Алгоритм мгновенного поиска

Question

Какие типы алгоритмов будут работать быстрее всего для поиска того, что ищется? Я понимаю, что это довольно близко к вопросу о том, как работает поиск в Google, но я не специалист по алгоритмам и все больше интересуюсь ими. Такой поиск выполняется с использованием суффиксных деревьев или чего-то подобного? Я думаю, что мне просто интересно запрашивать небольшие строки, в отличие от большого количества просканированных данных, как это делает Google.

Большое спасибо за любой вклад!

Answer 1

Для этих типов запросов вы можете хранить данные в Trie или в виде дерева Trie.

Answer 2

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

Вам нужно отсортировать массив.

Перейти к середине массива.Цикл: Если элемент массива меньше, чем tosearch, переходите к середине верхней половины;Иначе, если элемент массива больше, чем tosearch, переходите к середине нижней половины;иначе ты нашел это.и т. д.

var maxstep=Math.abs((Math.log(0.5)-Math.log(array.length))/Math.log(2)-1);

function searchinterval(tosearch,array){
         var len=array.length,
             pos=range=len/2,
             index=Math.round(pos),
             maxstep=.49999;
         for(var i=0;i<=maxstep;i++){
              range/=2;
              if(tosearch<array[index]){
                pos-=range;
                }
              else if(tosearch>array[index]){
                pos+=range;
                }
              else{
                return index;
                //you found it
                }
              index=Math.round(pos);
              }
         return false;
         }

Если поиск в массиве отсутствует, эта функция работает медленно.Имеется в виду семь циклов для длины массива 200 Я не уверен с максимальным количеством шагов или размером шага.

PS: Думаю, я нашел максимум шагов: (спасибо Maxima)

Log(0.5)-Log(array_length))/Log(2) -1); 

Answer 3

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