Как работает интеллектуальный ввод текста в смартфонах?
В нашей повседневной жизни есть мелочи, которые можно не замечать, пока кто-нибудь не спросит: «Как это работает?» Что ж, в этом посте позвольте мне поделиться с вами очень популярным алгоритмом в смартфонах, который предсказывает ваши слова, когда вы пишете текстовые сообщения.
Контекст
В вашем смартфоне, когда вы пишете текстовое сообщение в любом приложении или на веб-сайте, вы можете заметить, что определенный список слов появляется для выполнения ваших предложений. Иногда слова совершенно неожиданны, но иногда они действительно совпадают с нашими ожиданиями. Если его использовать с умом, это может помочь быстрее писать текст без опечаток. С другой стороны, некоторые люди отключают эту функцию, так как считают ее раздражающей.
В чем проблема?
Пока пользователь пишет текст, мы, как разработчики, хотим помочь ему/ей, показав список возможных слов, которые могут соответствовать идее, исходя из контекста, к которому ведет исходный текст. Итак, чтобы показать лучший список слов, мы берем два или три символа в качестве входных данных и смотрим в словарь, какие из них являются лучшими возможными словами (иногда двух или трех слов достаточно).
Некоторые зацепки
Я упомянул пару основных концепций, которые мы можем использовать, чтобы двигаться дальше. Во-первых, я упомянул ввод двух или трех символов, предоставленных пользователем. Второй — это концепция словаря, то есть набора всех возможных слов, которые могут существовать для данного языка. Для этого алгоритма мы должны определить, насколько близко слово в словаре к слову, которое ищет пользователь. Есть некоторые метрики, уже определенные теорией информации, такие как расстояние Левенштейна, которое подсчитывает количество различных символов, существующих между двумя словами. Мы можем взять три слова, где расстояние Левенштейна меньше, чем у других.
Структура данных для рассмотрения: Патрисия Трие
Основное дерево Патриции — это структура для хранения фрагментов слов (не слогов), которые могут быть общими для набора слов. Например, для следующих слов: война, предупреждение, боевой кабан, тепло, согревание — это Патрисия Трие.
Как видите, конструкция этого Trie позволяет построить все слова в списке и сохранить их алфавитный порядок. Способ восстановления списка слов — бег от корня к листу, добавляя каждую часть слов.
При поиске несуществующего слова The Patricia Trie покажет ближайшее слово, которое появляется в виде листа или узла, например, в приведенном выше примере, если мы ищем слово warn, хотя оно не появляясь в Trie, мы обнаружим, что теплый, согревающий и предупредительный являются наиболее близкими к нему словами.
Наконец, эта структура экономит много места в памяти, поскольку вам не нужно хранить каждое слово словаря в памяти. Вы храните только фрагменты слов, а в таких языках, как английский и испанский, много слов с одинаковыми символами.
Алгоритм
Теперь мы знаем, что Патрисия Триес обеспечивает отличную структуру для хранения набора слов, и мы можем узнать, является ли слово «ближайшим» к другому, используя расстояние Левенштейна в качестве эвристики. Перед запуском алгоритма нам нужно, чтобы эта структура работала:
Словарь, использующий все возможные слова данного языка и сохраняющий эту информацию в Patricia Trie. (Большинство словарей на английском языке включают в себя набор из 25 000 слов), поэтому он может жить в памяти без серьезных ограничений в любой системе.
Итак, вот алгоритм.
- Создайте слово для поиска, используя первые три символа, которые вводит пользователь.
- Найдите в словаре это искомое слово, если в словаре есть слово, совпадающее с ним, вернитесь. Ничего не показывайте пользователю.
- Если нет других одноуровневых узлов, то вернуть список слов в словаре в том же узле, пока он не станет первым листом.
- Если в словаре нет конкретного совпадения, получите родительский узел, который должен принести суженный список слов, очень близких к искомому слову.
- Возьмите одноуровневые узлы на этих уровнях и измерьте расстояние Левенштейна до искомого слова. Когда у вас есть три слова с минимальным расстоянием, верните эти слова.
- Если пользователь устанавливает новый символ в искомое слово, начните сначала с 1.
Примеры:
Берем ту же мини-конструкцию выше для небольшого списка слов. Давайте попробуем найти некоторые слова и посмотрим, как это
- Ищем слово «предупреждение». Этот случай очень прост. Поскольку слово действительно существует и является листом, оно ничего не возвращает. В следующих примерах я попытаюсь уточнить, что происходит с каждым символом, который пользователь добавляет в поиск. Как вы можете подумать, в этом примере я пропустил несколько промежуточных шагов, чтобы получить окончательный результат.
- В поисках слова «война»
- war является корневым узлом (с большим количеством дочерних узлов), а также соответствует слову в словаре. В этом случае алгоритм должен вернуть слово «война», а также ближайшие дочерние узлы. В данном случае «вархог» и «чернокнижник».
3. Поиск слова «варп»
- Давай последовательно. Алгоритм запускается, когда пользователь вводит первые три символа. Когда пользователь напишет «война», он принесет те же слова, что и в приведенном выше примере «война», «вархог» и «чернокнижник». Как только пользователь устанавливает окончательный p, слово поиска меняется на «warp», а затем предлагаются следующие слова: «warlock», «теплый» и «согревающий».
4. Найдите слово «политика»
- После первых трех символов «пол» появятся «война», «вархог» и «чернокнижник». После следующего символа будет вычисляться тот же набор слов. На самом деле, поскольку слово целиком не появляется в словаре, он будет выводить один и тот же список, если предлагать слова снова и снова.
Почему это работает?
Patricia Tries может хранить все возможные слова, что делает ее невероятно длинными и широкими деревьями в памяти. Хитрость здесь в том, что слова, которые мы добавляем в дерево, ограничены данным языком. Например, в английском языке около 25 000 слов, но в среднем человек ежедневно использует только 600 слов плюс спряжения глаголов. Невероятно похожие числа используются в испанском языке, хотя количество возможных слов превышает 25 000. На некоторых смартфонах есть Trie Patricia для каждого языка, и, основываясь на первых словах пользовательского текста, он пытается использовать один Trie чаще, чем другой.
Суть в том, что эта техника лучше работает в романско-латынских языках (таких как английский, испанский, итальянский, французский, немецкий и т. д.), но на самом деле в большинстве случаев она не работает с слоговыми языками, такими как японский, или языками без гласных, такими как иврит или ограниченное количество символов. алфавита, как гавайский. Некоторые диалекты невероятно трудно преобразовать в письменные слова
Некоторые улучшения
- Некоторые предсказатели слов, кроме простого словаря, имеют как минимум два. Один для вычисления слов, начиная с начала и другой, начиная в обратном порядке. Это может помочь найти слова, даже если пользователь пишет опечатки.
- Другими словами, предикторы учатся у пользователя. В приведенном выше примере пользователь пишет слово «политика», и оно не появляется в словаре, оно будет добавлено в «персональную версию» словаря для пользователя. В следующий раз, когда пользователь напишет «pol», обязательно будет слово «politics».
- Еще одно улучшение состоит в том, что специальная система Patricia Trie предназначена для глаголов и спряжений, другая — для сустантивов, еще одна — для прилагательных и т. д. В зависимости от контекста предложения эта система может предсказать, является ли следующее слово глаголом, а затем выполнить поиск в словарь глаголов; если слово является прилагательным, поиск в словаре прилагательных и так далее.
- Наконец, очистка и дезинфекция словаря, чтобы Trie был как можно меньше, чтобы повысить скорость поиска. Это можно сделать, определив семейства слов, чтобы сократить количество слов, хранящихся в словаре.
