Оптимальный способ найти аналогичное значение из большой таблицы

Question

У меня есть база данных, в которой я храню более 1000000 имен в MySQL. Теперь задача моего приложения немного типична. Я не только ищу имена в базе данных, но и нахожу похожие имена. Предположим, что имя введено как christian, тогда приложение покажет предложенные имена, такие как christine, chris и т. Д. Какой оптимальный способ сделать это, без использования предложения like. Предложения будут только об изменениях в последней части имени.

Answer 1

Если вам нужны похожие имена (по звуку), может помочь что-то вроде SOUNDEX(): http://dev.mysql.com/doc/refman/5.0/en/string-functions.html#function_soundex

В противном случае … LIKE 'chri%' кажется мне неплохой идеей?

Если выдействительно хотите только первые символы без LIKE, вы можете использовать SUBSTRING().

Answer 2

Вы можете использовать функцию php metaphone (), чтобы сгенерировать метафоновый код для каждого имени и сохранить их вместе с именами.

<?php
print "chris" . "\t" . metaphone("chris") . "\n";
print "christian" . "\t" . metaphone("christian") . "\n";
print "christine" . "\t" . metaphone("christine") . "\n";

# prints:
# chris      XRS
# christine  XRSTN
# christian  XRSXN

Затем вы можете использовать алгоритм расстояния Левенштейна (либо в php [http://php.net/manual/en/function.levenshtein.php], либо в mysql [http://www.artfulsoftware.com/infotree/queries.php#552])], чтобы вычислить расстояние между метакодами. В моем тесте расстояние ниже 2 или меньше показало уровень сходства. что вы ищете.

<?php
$names = array(
        array('mike',metaphone('mike')),
        array('chris',metaphone('chris')),
        array('chrstian',metaphone('christian')),
        array('christine',metaphone('christine')),
        array('michelle',metaphone('chris')),
        array('mick',metaphone('mick')),
        array('john',metaphone('john')),
        array('joseph',metaphone('joseph'))
);

foreach ($names as $name) {
        _compare($name);
}

function _compare($n) {
        global $names;
        $name = $n[0];
        $meta = $n[1];

        foreach ($names as $cname) {
                printf("The distance between $name and {$cname[0]} is %d\n",                          
                  levenshtein($meta, $cname[1]));
        }
}

Answer 3

Like, как правило, является хорошим решением, но другим способом повышения производительности может быть создание частичного индекса столбца, а затем отправка запросов той же длины, что и ваш префикс. См. MySQL документацию относительно col_name(length).

Answer 4

Использование LIKE, где левая сторона зафиксирована, не требует сканирования таблицы.Я предполагаю, что именно поэтому вы не хотите использовать LIKE: SELECT * FROM table WHERE name LIKE CONCAT(?, "%") быстро и не требует сканирования таблицы для поиска строк.CONCAT позволяет использовать подготовленные запросы с синтаксисом%.

Вы также можете сделать что-то вроде:

SELECT * from table WHERE name < 'christian' LIMIT 20

и

SELECT * FROM table WHERE name > 'christian' LIMIT 20

, чтобы найти соседей в отсортированномсписок.

Answer 5

Вы можете использовать SOUNDS LIKE, я думаю, что это должно быть довольно быстро.

http://dev.mysql.com/doc/refman/5.0/en/string-functions.html#operator_sounds-like

Answer 6

Думаю, вы могли бы использовать обычный эксперимент.Я не goot, но есть функция REGEXP, которую вы можете вставить в предложение WHERE.Смотрите здесь