Каков наилучший алгоритм автоматического поиска для JavaScript

Question

Скажем, у меня есть объект:

var names = ["john", "jane", "al", "mary", "zane" ... 1000+ Names]

Я хочу создать автоматическое предложение для поиска по этим именам.

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

Есть мысли?

Answer 1

Три было бы хорошим решением. Ваш набор данных будет выглядеть примерно так:

{"j":
    {"a":
        ["jacob", "jane", ..],
    {"o":
        ["john", "joesph", ..],
    ..
};

Вы должны индексировать символ за символом на столько уровней, насколько это разумно (чтобы самые внутренние массивы имели от 20 до 30 записей). Затем выполните простой поиск в массиве, хранящемся на самом внутреннем слое.

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

Answer 2

Почему бы вам не отсортировать массив с помощью Array.sort (), а затем выполнить бинарный поиск по нему?

Вот код, демонстрирующий бинарный поиск в js.

http://www.nczonline.net/blog/2009/09/01/computer-science-in-javascript-binary-search/

Также проверьте комментарии на странице, более эффективна реализация бинарного поиска

Answer 3

Я думаю, что trie - это естественный способ подумать об автоматическом предложении из большого пула - вам нужно выполнить поиск по префиксу, и он пытается в этом преуспеть. Тем не менее, я действительно не уверен, как базовая реализация массивов работает в javascript, поэтому вам придется сравнить ее и посмотреть, в какой момент три становится эффективным. То есть, вероятно, есть некоторое число n, ниже которого имеет смысл выполнять линейный поиск по сравнению с использованием дерева. В довершение всего, так как каждый браузер использует свой механизм js, эффективность этого, вероятно, будет отличаться.

Тем не менее, вот реализация trie в js: http://notdennisbyrne.blogspot.com/2008/12/javascript-trie-implementation.html

Если массивы js работают так, как я думаю (например, в качестве причудливых хеш-таблиц, что означает, что даже выполнение trienode [10] в конечном итоге приведет к поиску хеш-таблицы), то еще один простой вариант, который следует рассмотреть, - хранить каждый префикс слово в массиве. например для имени john вы вставите j jo joh john в массив, это даст вам постоянный поиск по времени, но, конечно, будет использовать много памяти.

Answer 4

Если вы хотите найти Яна в Джоне, взгляните на функции PHP soundex и metaphone.Эта функция преобразует строку в фонетическую строку.На http://php.net приведены некоторые примеры, которые вы можете легко преобразовать в JS.Вы рады - в английском нет специальных символов.

Создайте второй массив с этим фонетическим выравниванием и добавьте указатель на элемент источника.Вам нужно мультисортировать второй массив.https://stackoverflow.com/a/9374631/817152

Переведите и слово для поиска.

Затем используйте алгоритм интервального поиска, чтобы быстро.https://stackoverflow.com/a/16371484/817152

Не сдавайся.

Answer 5

Вы можете использовать автозаполнение фреймворка Jquery UI. Вы найдете документацию здесь .
Это позволит вам переделать колесо ...