Нужен алгоритм для создания Google, как поиск слов

Question

Я объясню проблему здесь.

Предположим, у меня есть список из 1000 слов. Скажем, это словарь. Пользователь вводит какое-то слово, и оно будет соответствовать точному совпадению, если это слово правильно или дать самое близкое совпадение. Подобно поиску Google, поскольку мы вводим что-то, и это дает самое близкое соответствие.

алгоритм, который я думал, что это

Read the word list one by one 
split our input word string into characters 
take the first word from the list and match character wise 
similarly do it for other words in the list 

Я знаю, что это долгий путь, и это займет много времени. Есть ли кто-нибудь знает, как реализовать лучший алгоритм

Answer 1

1. Сортировать слова в массиве
2. Когда слово приходит => бинарного поиска (журнал (п)) (мы делаем это потому, что если вы используете хэш-таблицу это будет хорошо для прямого матча, но плохое для смежно)
3. Если идеальный матч вернуть его
4. Else вычислить levensthein distance запрашиваемого слова с соседними словами и их соседей (которые должны быть определены) и добавить их в список return (если они удовлетворяют)
5. Возвращает список смежных слов selec Ted

Быстрая и грязная реализация с /usr/share/dict/words (вы все еще должны сделать levensthein расстояние часть и выбор)

Отказ от ответственности: Двоичный код поиска заимствованные из http://www.perlmonks.org/?node_id=503154

open(FILE, "<", "/usr/share/dict/words"); 
my @lines = <FILE>; 
my $word = $ARGV[0]; 

sub BinSearch 
{ 
    my ($target, $cmp) = @_; 
    my @array = @{$_[2]}; 

    my $posmin = 0; 
    my $posmax = $#array; 

    return -0.5 if &$cmp (0, \@array, $target) > 0; 
    return $#array + 0.5 if &$cmp ($#array, \@array, $target) < 0; 

    while (1) 
    { 
     my $mid = int (($posmin + $posmax)/2); 
     my $result = &$cmp ($mid, \@array, $target); 


     if ($result < 0) 
     { 
      $posmin = $posmax, next if $mid == $posmin && $posmax != $posmin; 
      if ($mid == $posmin){ 
       return "Not found, TODO find close match\n"; 
      } 
      $posmin = $mid; 
     } 
     elsif ($result > 0) 
     { 
      $posmax = $posmin, next if $mid == $posmax && $posmax != $posmin; 
      if ($mid == $posmax){ 
       return "Not found, TODO find close match\n"; 
      } 
      $posmax = $mid; 
     } 
     else 
     { 
      return "Found: ".@array[$mid]; 
     } 
    } 
} 
sub cmpFunc 
{ 
    my ($index, $arrayRef, $target) = @_; 
    my $item = $$arrayRef[$index]; 
    $item =lc($item); 
    $target =lc($target); 
    $a = $item cmp $target; 
    return $a; 
} 

print BinSearch($word."\n", \&cmpFunc, \@lines)."\n"; 

Использование (если сценарий называется find_words.pl):

perl find_words.pl word

Где слово - это слово, которое вы хотите найти.

Answer 2

Общим алгоритмом для такого поиска «нечетких» слов является Levenshtein distance. Он не находит похожих слов, но вычисляет сходство слов. Эта оценка подобия (или расстояние Левенштейна) затем может использоваться функцией сортировки или фильтрации для выбора похожих слов.

Как измеряется расстояние просто: сколько символов необходимо изменить от целевого слова до совпадающего слова. Например, расстояние 3 означает, что разница между словами составляет 3 редактирования (не обязательно символы, так как она также включает в себя действие добавления и удаления символов).

Сайт Rosetta Кодекс имеет список алгоритмов дистанционных Левенштейн, реализованных на различных языках, в том числе Tcl и Perl: http://rosettacode.org/wiki/Levenshtein_distance

Существует страница на вики в tcler, что обсуждаются алгоритмы подобия, которое включает в себя несколько реализаций расстояния Левенштейна: similarity

Для Perl есть также модуль CPAN, который вы можете использовать: Text::Levenshtein

Так Perl'е вы можете просто сделать:

use Text::Levenshtein; 

my %word_distance; 
@word_distance{@dictionary} = distance($word,@dictionary); 

Затем перейдите в хэш для word_distance, чтобы найти наиболее похожие слова.

Answer 3

Проблема с использованием простого бинарного поиска для получения окрестности подобных слов, а затем с использованием алгоритма Левенштейна для уточнения заключается в том, что ошибки могут возникать как в начале слова, так и позже; вы рискуете полностью потерять слова, где есть ранняя ошибка. Более эффективным методом может быть использование алгоритма Soundex для создания ключей сортировки в списке слов, чтобы вы выполняли поиск по основному подобию. Затем вы можете использовать Levenshtein для уточнения, но взвешивая, что сходство измеряется редкостью слов в базовом исходном корпусе; предполагая, что пользователи с большей вероятностью захотят получить общее слово, чем редкое, это полезная мера. (Предполагается, что у вас есть исходный корпус, но если вы хотите подражать Google, то у вас определенно есть один из них.)

Возможно, было бы лучше посмотреть на способы использования некоторых своего рода механизм уменьшения карты для запуска взвешенной метрики расстояния Левенштейна по всему набору слов. Это больше похоже на подход «бросить оборудование по проблеме», но позволяет избежать проблем, связанных с потенциальными проблемами со словами, пропущенными из-за начального фильтра. Увы, это означает, что вы получите то, что нельзя оттолкнуть как часть простой части программного обеспечения (системы обеспечения поддержки для чего-то вроде этого вряд ли будут тем, что вы хотите навязать обычный пользователь), но, вероятно, будет целесообразно развертывать службу.