q-грамм приблизительные оптимизации соответствия

Question

q-грамм приблизительные оптимизации соответствия

У меня есть таблица, содержащая 3 миллиона человек записи, на которых я хочу выполнить нечеткое соответствие с помощью q-граммов (на фамилии, например). Я составил таблицу 2 граммов, связывающихся с этим, но поисковая производительность не является большой на этом объеме данных (приблизительно 5 минут).

У меня в основном есть два вопроса: (1) можно ли предложить какие-либо способы улучшить производительность для предотвращения сканирования таблицы (т.е. имеющий необходимость считать общие q-граммы между строкой поиска и 3 миллионами фамилий) (2) С q-граммами, если A подобен B, и C подобен B, это подразумевает, что C подобен A?

С уважением

Peter

6

sql sql-server fuzzy-search fuzzy-comparison

задан pnuts 24 November 2015 в 23:49

2 ответа

Другие вопросы по тегам:

sql sql-server fuzzy-search fuzzy-comparison

Похожие вопросы:

score 6 · Answer 1

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

Я полагаю, что вас интересуют только те строки, для которых расстояние редактирования меньше заданного значения. И ваши q-граммы (или n-граммы) выглядят следующим образом

2-grams for "foobar": {"fo","oo","ob","ba","ar"}

Вы могли бы использовать позиционные q-граммы:
```
 "foobar": {("fo",1),("oo",2),("ob",3),("ba",4),("ar",5)}
```
Позиционная информация может быть использована для определения того, является ли совпадающая q-грамма действительно является "хорошим совпадением".

Например, если вы ищете "foobar" с максимальным расстоянием редактирования равным 2, это означает, что вас интересуют только те слова, в которых интересуют слова, в которых
```
2-грамма "fo" существует в позиции от 1 до 3 или
2-грамма "oo" существует в позиции от 2 до 4 или
... и так далее
```
Строка "barfoo" не получает никаких совпадений, потому что позиции других совпадающих 2-грамм отличаются на 3.
Также, возможно будет полезно использовать связь между расстоянием редактирования и количеством совпадающих q-грамм. Суть в том, что поскольку

строка s имеет len(s)-q+1 q-грамм

и

одна операция редактирования может затрагивать не более q q-грамм,

мы можем вывести, что

строки s1 и s2 на расстоянии редактирования d имеют по меньшей мере max(len(s1),len(s2))-q+1-qk совпадающих непозиционных q-грамм.

Если вы ищете "foobar" с максимальным расстоянием редактирования 2, то подходящая 7-символьная строка (например "fotocar") должна содержать по крайней мере две общие 2-граммы.
Наконец, очевидная вещь, которую нужно сделать, это фильтровать по длине. Расстояние расстояние между двумя строками равно как минимум, разность длин этих строк. Например, если ваш порог равен 2, и вы ищете "foobar", "foobarbar" не может явно совпасть.

См. http://pages.stern.nyu.edu/~panos/publications/deb-dec2001.pdf для получения дополнительной информации и некоторых псевдо SQL.

score 2 · Answer 2

Интересный документ об индексировании q-граммов ДНК, чтобы не сканировать всю таблицу:

www.comp.nus.edu.sg/~atung/publication/qgram_edit.pdf