Самый быстрый способ сопоставить аббревиатуру со словарем

Question

Аббревиатура - это строка буквенно-цифровых символов. Цифры обозначают количество пропущенных букв, например, i18n является сокращением интернационализации. Итак, inter15 и 20. Скажем, у вас есть словарь слов, какой самый быстрый способ найти все слова в словаре, которые соответствуют данной аббревиатуре? Вы можете использовать любую структуру данных, которая вам нравится для вашего словаря, но алгоритм поиска совпадающих слов должен быть лучше, чем O (n), где n - количество слов в словаре.

Answer 1

Решение было бы категоризировать все слова в нескольких массивах. Каждый массив содержит все слова, которые содержат определенное количество букв. Например массив со словами 4 букв, таких как: продукты питания, дерево, как, щука и т.д. и прочей с 5 букв слова и т.д. и т.п.

Так с i18n языке Генеральный Общие Аббревиатура, вы разделите символов и числа: «в» «18», и вы добавляете количество символов к числу: 2 + 18 = 20. Теперь вы знаете, что ваше слово находится в массиве слов с 20 буквами.

Я думаю, что мы можем сделать лучше, но это лучше, чем поиск слова во всей словарной статье.

Answer 2

Вот идея для дерева a10n (дерево сокращений, или должно быть a10n t2e?).

Пропущенные буквы заменяются длиной недостающего куска, поэтому длина матча известна заранее. Имеет смысл разделить словарь в суб-словарей, которые содержат слова постоянной длины:

dict -> dict2 -> {ad, ah, am, an, as, at, ...} 
    -> dict3 -> {abe, abo, abu, ace, act, ada, add, ... } 
    -> dict4 -> {abba, abbe, abby, ...} 
    -> ... 

Каждый из этих словарей содержит упорядоченный список слов. Если аббревиатура, скажем, «5», верните этот список для субдикта длиной 5. Если аббревиатура «зеленая», т. Е. Аббревиатура вообще, проверьте, находится ли это слово в списке, используя двоичный поиск.

С учетом тривиальных случаев мы должны найти способ быстро найти этот список. Давайте представим дерево с позицией и буквой. Первый уровень дерева относится к положению буквы, второго уровня к самому письму, так же, как в синтаксическом дереве, например:

dict3 -> i == 0 -> a -> {ant} 
       -> b -> {bat, bee} 
       -> c -> {cat, cod, cow} 
       -> ... 
      i == 1 -> a -> {bat, cat, rat} 
       -> b -> {} 
       -> c -> {} 
       -> ... 

Теперь найти пересечение списка всех заданных букв. Если мы ищем «c2», возьмем список в (0, c). Если мы ищем «b1t», мы берем пересечение списков в (0, b) и (2, t). Когда списки упорядочены, поиск пересечения должен быть достаточно быстрым.

Есть и другие подходы. Tries - это структура данных, которая позволяет нам быстро искать словари. Я сказал в комментарии к удаленному сообщению, что я не думаю, что попытки - это подходящая структура данных в этом случае, потому что попытки хороши для поиска слов, когда известны первые буквы. Но я не уверен теперь: можно было бы спуститься во все ветви три, когда будет найден шаблон, т. Е. Недостающее письмо. Для слова типа «i18n» количество ветвей кажется довольно большим, но на практике будет много нулевых ветвей. В моем (маленьком) тесте теста около 45 000 слов нет слова «i18n», даже интернационализации. Таким образом, для реальных словарей попытки могут быть даже вариантом.

(Извинения пользователя, удаляемого ответ, но я говорил одному синтаксическое дерево для Dict в моем комментарии. Суб-нах для каждой длины могут работать, если словарь не зверский.)

Answer 3

Так у вас есть запрос prefix - count - suffix. Есть несколько способов сделать это.

Если префикс никогда не будет пустым, вы можете построить дерево префикса (это просто trie) и запросить его для всех слов, начинающихся с этого префикса, для тех, у кого есть запрошенная длина и суффикс.

Вы можете сделать то же самое, построив generalized suffix tree.

Или, поскольку префикс или суффикс могут быть пустыми, вы можете создать дерево префикса и дерево суффикса. Выполните запрос как для фильтрации, так и для объединения результатов.

Возможно, вы можете построить единое дерево префикса-суффикса. Структура данных будет несколько более сложной, чем наличие двух отдельных деревьев, но для этого потребуется меньше памяти.

Как я помню (это было несколько лет), вы можете делать все это и многое другое (искать слова с отсутствующими буквами и т. Д.) С помощью графического графика ациклического графика (DAWG).