Поиск определенной строки с полем ошибки
Как я могу найти конкретный string с погрешностью?
Пример:
у меня есть table со следующим values:
Таблица брендов
- Бренд: Panasonic, Модель: 15T
- Бренд: Apple, Модель: IPHONE 7
- Бренд: Samsung, Модель: Galaxy S8
- Бренд: Microsoft, M15
И я хочу найти совпадение с полем из 3 неправильных символов.
Для примера мой ввод M $ crosoft, и я хочу, чтобы он возвратил Microsoft row, Или, если я введу Pnasonic, он должен ввести Panasonic row,
Как я могу достичь этого без ущерба для производительности?
Легкий путь — сравнить каждого из персонажей и счетчик трех ошибок, но мне нужна производительность, так как бренды table имеет около 200K + rows.
Я пишу в PHP.
Решение
Возможно, вы захотите использовать комбинацию Метафона и Левенштейна. (для орфографических ошибок)
http://php.net/manual/en/function.metaphone.php
А также
http://php.net/manual/en/function.levenshtein.php
Метафон работает со звуками, поэтому «плохой» пример — это то, что вы можете думать об этом как об удалении гласных и замене некоторых составных звуков на отдельные буквы (почти как сокращение). Итак, используя ваш пример
$sound1 = metaphone('M$crosoft');
echo "$sound1\n";
$sound2 = metaphone('Microsoft');
echo "$sound2\n";
Выходы
MKRSFT
MKRSFT
Как вы можете видеть, они совпадают.
Вы можете проверить это здесь
http://sandbox.onlinephpfunctions.com/code/716471f5fed18268a2dc0aea800b3db634d9616f
Спектакль В связи с дополнительными затратами на запуск метафона я бы предложил предварительно вычислить индекс звука, слова, по которым вы будете искать ранее, и сохранить их в базе данных. Затем, когда вы запускаете поиск пользователя, вы запускаете то же самое metaphone использовать их поисковые слова и использовать их для поиска по звуковому указателю в таблице. Таким образом, вы загружаете расходы на создание индекса звука и должны сделать это только один раз (или когда записи редактируются).
Тем не менее, вы можете найти соответствие слишком свободно, и в этом случае вы можете использовать Левенштейна. Это вычисляет разницу между двумя словами на основе необходимых изменений. Такие, как вставка обновлений и удаление, которые необходимо сделать, вы даже можете взвесить операции.
$len = levenshtein ('M$crosoft', 'Microsoft');
echo "$len\n";
//as you can see the arguments are $str1, $str2, insert cost, replace cost, delete cost
//so we can control what weight we get for each operation.
$len = levenshtein ('M$crosoft', 'Microsoft', 1,2,1);
echo "$len\n";
Выходы
1
2
Теперь, если вам нужно объединить это с «кучей» текста, которая может быть очень сложной, вам придется использовать полнотекстовый поиск в БД.
Это не тривиально.
Возможно, лучшим выбором было бы рассмотреть использование чего-то вроде Sphinx, который представляет собой механизм полнотекстового поиска. Это не сложно, чтобы получить базовую настройку, как. Но это не будет волшебной пулей, так что вам придется делать некоторые вещи, такие как: stemming, wordforms и т.д ..
Опять же, не тривиально, но у него полнотекстовый поиск гораздо лучше, чем в Mysql DB,
Спектакль Я могу сказать вам, что это быстро, возможно, в 20 раз быстрее, чем MySql при поиске текста, но у него есть свои особенности. Но я очень рекомендую это. Мы выполняем около 150 тыс. Запросов через наш небольшой кластер сфинксов в минуту на рекордном наборе в 1/4 миллиона строк. (наш главный сервер 12-ядерный, 54GB монстр)
У этого типа поиска нет единого надежного решения проблемы огня, или, по крайней мере, я его еще не нашел (и я сделал тонну этого).
Другие решения
Других решений пока нет …