Блог

Как быстро выполнить поиск в списке, который содержит 40 миллионов слов?

Мне нужно найти слова, содержащие как минимум 4 буквы, которые я указал перед продолжением.

Пример: в списке всего несколько слов:

 dogging
dopping
baobabisaneviltree
  

Мои конкретные буквы в строковом формате ‘odxxini’. Мне нужно найти любые слова, содержащие любые (4 ) символы из моей строки.

Результат:

 dopping
dogging
  

(потому что оба слова содержат ‘o’ ‘d’ ‘i ‘ ‘n’)
Надеюсь, я хорошо объяснил. Извините за английский. Пожалуйста, исправьте ошибки.

Если у кого-нибудь есть какие-либо знания об этой проблеме, я буду рад его услышать. 🙂

Я написал до сих пор (потому что это начало ..) этот код:

 private void seeksearcher()
        {
            double counter = 0, k=0;
            double licznik = (double)listwords.Capacity;

            char[] letterarray = stringletters.ToCharArray();
            foreach(String word in listwords)
            {

                for(int i=0;i<letterarray.Length;i  )
                    if(word.Contains(letterarray[i]))
                        counter  ;
                if(counter > 4)
                    textBox2.Text =word   Environment.NewLine;

            }
        }
  

Я почти уверен, что сложность сейчас n * 7n, она ужасно большая : (

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

Давайте предположим, что размер каждого набора решений очень мал по сравнению с размером словаря.

Давайте также предположим, что размер каждой записи в словаре невелик; у вас там нет слов из десяти тысяч букв или чего-то глупого в этом роде.

Учитывая эти два ограничения, большой вопрос в том, требуется ли вам сублинейное время поиска?

Алгоритмы линейного времени просты. Например:

• отсортируйте символы каждого слова из лексикона в алфавитном порядке.
• отсортируйте символы запроса в алфавитном порядке
• выполните сравнение последовательности отсортированного запроса с каждым словом отсортированного словаря.

То есть, предположим, у вас есть лексикон

 STOPPING
POTSHARD
OPTING
DECORATE
  

и запрос TOPSXZ . Отсортируйте запрос по символам: OPSTXZ . Теперь просмотрите словарь, отсортировав его по символам:

 STOPPING --> GINOPPST
POTSHARD --> ADHOPRST
OPTING   --> GINOPT
DECORATE --> ACDEEORT
  

И теперь легко определить, есть ли у вас четыре или более совпадений; вы просто запускаете алгоритм самой длинной общей подпоследовательности в OPSTXZ и GINOPPST и обнаруживаете, что самой длинной общей подпоследовательностью является OPST , состоящая из четырех букв, так что она совпадает. Самая длинная распространенная подпоследовательность OPSTXZ и ADHOPRST также OPST , поэтому она обрабатывается. Самая длинная общая подпоследовательность OPSTXY и GINOPT равна OPT , то есть всего трем, а самая длинная общая подпоследовательность OPSTXY и ACDEEORT — OT , то есть всего двум.

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

Теперь, если вам нужно сублинейное решение, при котором вы заранее исключаете из рассмотрения кучу этих 40 миллионов слов из лексикона, это будет сложнее. Вам требуется сублинейное решение?

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

Например, у вас могут быть указатели на все слова, содержащие букву d, затем указатели на все слова, содержащие букву o. И т.д. Тогда вы получите гораздо меньший список, который вам будет легче искать, найдя пересечение ваших букв (слов, в которых есть все нужные вам буквы).

Конечно, это просто перемешивает работу, заставляя ее выполнять большую обработку заранее, а не во время поиска.

Можете ли вы заранее проиндексировать слова? Я бы начал с индексации списка слов, создав отсортированный список слов для каждого символа:

 a: baobabisaneviltree
b: baobabisaneviltree
c: 
d: dogging, dopping
e: etc
  

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

 dogging: 4
dopping: 4
dapper: 1
  

Затем я бы прошелся по словарю в поисках чисел, превышающих 4.

Если вы не можете проиндексировать, то ваше решение настолько хорошо, насколько вы можете получить. Вам обязательно нужно посмотреть на каждую букву в каждом слове (O (n * m)), чтобы увидеть, появляется ли данная буква в слове, затем вам нужно проверить наличие каждой буквы. Одна из проблем с вашим решением заключается в том, что вы будете добавлять слово в текстовое поле несколько раз, возможно, вам захочется сделать это if(counter == 4) .

Забавный код (непроверенный):

 // With 40 million words this can use a lot of space.  You would probably
// want to create the index on disk and maybe the intermediate processing
// as well.
var index = wordList.SelectMany(word => word.ToCharArray(), 
                                (word, character) => 
                                  new { word, character})
                    .ToLookup(x => x.character, x => x.word);
var result = letterArray.Distinct()
                        .SelectMany(c => index[c])
                        .GroupBy(word => word)
                        .Where(word => word.Count() > 4)
                        .Select(word => word.Key);