Как найти и вывести контакты с возможными опечатками?

Question

[Джамалудин Османов]

Есть База данных MySQL с таблицей контактов
со столбцами id и name (350000 контактов). Необходимо их собрать в группы контактов с возможными опечатками.
Например:
Тимур
Дмитрий
Линар
Линур
Темур
Димитрий
Легар

Нужно собрать и вывести:
Тимур, Темур
Дмитрий, Димитрий
Линур, Линар, Легар.

На опечатки проверял с помощью функции levenshtein()<2.

Можно было бы перебрать массив один раз и выдать результат. Но проблема в том что база данных контактов постоянно меняется и изменяется. И нужен всегда актуальный вариант(по крайней мере актуальный на каждые 5-10 минут), но учитывая, что перебор составляет очень большое количество времени (1.3 контакта в секунду) это не позволительно. Подскажите пожалуйста каким образом можно реализовать данную задачу. Или оптимизировать поиск.

Поиск выполнял следующим способом:
1. Запрашивал контакты из бд
2. Каждый контакт проверял с каждым на возможность опечатка "левенштейном"

Comments

[iljaGolubev]

Не думаю, что в mysql эта задача решается. При большом количестве строк будет медленно. Для быстрого поиска лучше использовать специальзированные инструменты.
Посмотрите для начала тут.

Answer 1

[d-stream]

Первое что напрашивается - отфильтровывать явно несравнимые. Например какой смысл сравнивать трехбуквенное имя с пятнадцатисимвольным?

Ну и общий вопрос: а в каком из имен Тимур, Темур и Теймур опечатка?

Comments

[Джамалудин Османов]

Опечатка не обязательно должна быть. Необходимо вывести контакты с возможными опечатками

Answer 2

[Сергей]

Но проблема в том что база данных контактов постоянно меняется и изменяется. И нужен всегда актуальный вариант(по крайней мере актуальный на каждые 5-10 минут), но учитывая, что перебор составляет очень большое количество времени (1.3 контакта в секунду) это не позволительно.

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

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