Ищите структуру данных, чтобы соответствовать словам по буквам

Question

Учитывая список строчных слов, каждое слово одинаковой длины и множество шаблонов, каждый из которых содержит несколько букв в некоторых позициях, а другие буквы неизвестны, найдите все слова, соответствующие каждому шаблону.

Например, список слов:

["ixlwnb","ivknmt","vvqnbl","qvhntl"]

И шаблоны:

i-----
-v---l
-v-n-l

С наивным алгоритмом можно выполнить O (NL) путешествие для каждого шаблона, где N количество слов, а L - длина слова.

Но поскольку в одном и том же списке слов может быть много шаблонов, существует ли какая-либо хорошая структура данных для предварительной обработки и сохранения списка слов, а затем достаточно соответствие для всех шаблонов?

Answer 1

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

Теперь ваш инвертированный индекс: для каждой буквы в каждой позиции создайте отсортированный список идентификаторов для слов, у которых эта буква находится в этом месте.

Чтобы выполнить поиск, вы берете списки идентификаторов для каждой буквы в заданных вами позициях и берете пересечение списков, используя алгоритм, подобный «слиянию» в сортировке слиянием. Все идентификаторы в пересечении соответствуют вводу.

В качестве альтернативы, если ваши слова достаточно короткие (12 символов или меньше), вы можете сжать их в 64-разрядные слова (используя 5 бит на букву, с буквами 1-26). ). Создайте битовую маску с двоичным кодом 11111 в местах, где у вас есть буква, и 00000 в местах, где у вас есть пробел. И битовый тест из вашего ввода с 5-битным кодом для каждой буквы в каждом месте, используя 00000, где у вас есть пробелы. Например, если вы введете a-c, тогда ваша битовая маска будет двоичной 111110000011111, а ваша двоичная битовая 000010000000011. Go через ваш список слов, возьмите этот битовый and каждого слова с битовой маской и проверьте, равно ли оно значению битового теста. Это дружественно к кешу, а внутренний l oop тесен, поэтому может быть конкурентоспособен с алгоритмами, которые выглядят так, как будто они должны быть быстрее на бумаге.

Answer 2

Я буду предварять это большим количеством комментариев и меньшим количеством ответов (хотя у меня недостаточно репутации, чтобы комментировать). Я не могу думать о какой-либо структуре данных, которая будет удовлетворять требованиям коробки. Интересно было подумать, и я решил поделиться одним потенциальным решением, которое всплыло в моей голове.

Я набрал часть «той же длины» и подумал, что могу придумать что-нибудь на основе этого. .

Теоретически у нас может быть N (N - длина) отображений char -> set. Когда строки добавляются, он проходит через каждый символ и добавляет строку в соответствующий набор. psuedocode:

firstCharMap[s[0]].insert(s);
secondCharMap[s[1]].insert(s);
thirdCharMap[s[2]].insert(s);
fourthCharMap[s[3]].insert(s);
fifthCharMap[s[4]].insert(s);
sixthCharMap[s[5]].insert(s);

Затем, чтобы определить, какие строки соответствуют шаблону, мы просто сделаем пересечение множеств ex: "-vnl" будет: пересечение множеств: secondCharMap [v], четвертыйCharMap [n ], sixthCharMap [l]

Один крайний случай, который выпадает, - это если я хочу просто получить все строки, так что если это требование - нам также может понадобиться дополнительный набор всех строк.

Это решение кажется неуклюжим, но я думаю, что оно может работать. В зависимости от языка, количества строк и т. Д. c - я не удивлюсь, если он будет работать хуже, чем просто перебирать все строки и проверять предикат.