Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Индексирование строк для нечеткого поиска

Автор: Maksym 29.6.2007, 20:41

Итак. Есть таблица -- 500 000 строк, для начала. Есть входная строка. Необходимо максимально эффективным способом выбрать все строки из таблицы, для которых дистанция между ними и входной строкой меньше некотрого заданного значения. Дистанция между двумя строками определяется как минимальное число атамарных операций изменения первой строки (удаление/ вставка/замена символа), с помощью которых ее можно трансформировать во вторую. На данный момент это делается тупо перебором и применением алгоритма Левенштайна для каждой строки и входной строки. Понятно, что это крайне не эффективно (да и работает долго  ).  Напрашивается создание индекса, который бы можно было использовать для нечеткого поиска. Задача эта, насколько я понимаю, известная. Google дает много математики в ответ на запрос и математики нетривиальной.  Никакого общепринятного единого решения я не нашел.   Есть ряд мыслей в разработке, но красивого решения нет. Что предложите вы, дорогие софорумчане?    ЗЫ. БД Oracle, язык Java.

Автор: maxim1000 29.6.2007, 22:11

первое, что пришло в голову: возьмём количество букв "а" в строке если было сделано n преобразований, то количество не может измениться больше, чем на n т.е. можно по этому критерию делать отсечение по идее, хорошо будет работать, только когда n<<длины строки конечно же, следующий шаг - переход к статистике по каждому символу P.S. хотя не очень мне эта мысль и нравится, но вдруг пригодится... Добавлено через 8 минут и 3 секунды а... вот почему она мне не нравится: много букофф  даже если у нас длина строки - около 100 и используются только латинские буквы, то среднее количество вхождений каждой буквы будет меньше 4 (конечно же, для каких-то букв частота будет выше, для каких=то - ниже), даже при допустимом количестве изменений 5, скорее всего, хорошие отсечения будут встречаться очень редко есть ещё один вариант: делим все значения символа на две группы (желательно, чтобы в среднестатистической строке количество символов из каждой группы было приблизительно половина) и наша характеристика - количество в строке символов из первой группы (ну или второй, например) соответственно выбираем из таблицы все строки с характеристикой X+/-n P.S. неплохо было бы узнать какие-то оценки для средней длины строк и допустимого количества трансформаций

Автор: Maksym 30.6.2007, 11:37

maxim1000 спасибо за ответ Цитата(maxim1000 @  29.6.2007,  22:11 ) неплохо было бы узнать какие-то оценки для средней длины строк и допустимого количества трансформаций  Средняя длина строк -- 20-25 симовлов. Допустимое количество трансформаций -- параметр.

Автор: ivashkanet 4.7.2007, 10:38

Maksym, а насколько осмысленные данные лежат в таблице и входной строке? Насколько осмысленным будут эти трансформации? Например, если трансформации не затрагивают количество слов (трансформируются только формы слов: окончания, суффиксы, приставки) , то можно индексить это количество. В общем, хотелось бы более конкретные данные о самих строках и их трансформациями. Добавлено через 1 минуту и 11 секунд Цитата(maxim1000 @  29.6.2007,  22:11 ) и наша характеристика - количество в строке символов из первой группы (ну или второй, например) соответственно выбираем из таблицы все строки с характеристикой X+/-n Мне эта идея нравится    maxim1000, +1

Автор: Maksym 5.7.2007, 12:32

Цитата(ivashkanet @  4.7.2007,  10:38 ) а насколько осмысленные данные лежат в таблице и входной строке? Насколько осмысленным будут эти трансформации? Например, если трансформации не затрагивают количество слов (трансформируются только формы слов: окончания, суффиксы, приставки) , то можно индексить это количество. В общем, хотелось бы более конкретные данные о самих строках и их трансформациями. Это фамилии, но национальная принадлежность произвольная, встречается страшный бред. Трансформации, по сути, -- это описки, опечатки, транслитерации с других языков и т.п. Сейчас работаем в направлении построения битовых сигнатур. Смысл метода в следующем: - каждому слову ставим в соответствие битовый вектор, например длины 26. - включенный бит на позиции n означает что n-ая буква латинского алфавита присутствует в слове Удобное свойство этой сигнатуры в том, что одна трансформация исходного слова влечет за собой изменение числа бит в сигнатуре не более чем на один... Длину сигнатуры можно уменьшить, чтобы снизить комбинаторику и упростить вычисления, например за счет сведения частых букв к одной позиции в сигнатуре... Пока практического результата нет, идет research. Буду рад любым вашим мыслям и идеям. ЗЫ. Попытка применить метод http://itman.narod.ru/articles/ps_pdf_txt/qgram_dbms.pdf существенного прироста производительности не дала, хотя сам по себе метод интересный и заслуживает внимания для близких задач.

Автор: Maksym 9.7.2007, 13:02

Уточнение к постановке задачи: Операция изменения таблицы происходит один раз в сутки (централизованный update из другого источника данных). Обращение к операции нечеткого поиска (которую и нужно оптимизировать) -- десятки тысяч раз в сутки.

Автор: snooker2 8.8.2007, 10:24

Работаю над аналогичной задачей. Левенштейн годится когда строки (эталон и где ищем) примерно одной длины, если разница большая, то он малоэффективен (личное мнение). Разработал алгоритм подсчета количества вхождений сочетаний символов одной строки в другую, то есть берем, к примеру, три первых символа в первой строке и находим их во второй, сдвигаемся   на одну позицию вправо в первой строке и берем очередные три символа, снова ищем во второй и так далее, подсчитывая количество совпадений. Алгоритм медленный, но дает достаточно высокую степень распознования. Тема очень для меня актуальная, буду рад пообщаться более конкретно. Мой ICQ 14099319.

Автор: ProgBeat 8.8.2007, 19:07

Я так понимаю задача найти не оптимальное решение, а эффективное на практике, так?

Автор: snooker2 9.8.2007, 08:19

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

Автор: ProgBeat 9.8.2007, 21:49

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

Автор: ProgBeat 9.8.2007, 22:34

есть хорошая книга почти на эту тему: "Дэн Гасфилд  Строки,  деревья  и последовательности  в алгоритмах Информатика и вычислительная биология" но в ней некоторые алгоритмы, больше расчитаны на какуюто фигню типа последовательности днк и тд, а не русского текста... но разницы почти нет.... )

Автор: snooker2 10.8.2007, 10:15

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

Автор: snooker2 10.8.2007, 10:52

Можно ли где-нибудь скачать книгу Гасфилда?

Автор: ProgBeat 10.8.2007, 15:06

где скачать не знаю... у меня бумажный вариант... возможно в файлообменных сетях можно нарыть....  можно поискать метод BLAST (када читал не асилил) но насколько я знаю он хорошо себя зарекомендовал для поиска биологических последовательностей...  о эффективном применении для поиска почтовых адресов с помощью него не слышал... (но возможно и в этом он себя зарекомендует кагданибудь) а какие размеры данных нужно обрабатывать ? сколько адресов, средняя длина адреса, средняя длина запроса? хоть приблизительно порядок 10000, 1000000 адресов? может данные можно однозначно разбить на группы?

Автор: Maksym 14.8.2007, 17:53

В моем случае проблема решилась с помощью построения отдельного индексного файла для всех строк таблицы после каждого её изменения. Файл содержал для каждой строки набор битовых сигнатур, находящихся от этой сроки на заданном расстоянии. Таким образом при поиске для входной строки строились все возможные битовые сигнатуры, находящиеся на заданном расстоянии, и осуществлялся поиск на совпадение в этом индексном файле. Такая операция отсекала большее число записей, а по оставшимся проходили Левенштайном. Фишка тут в том, что индексный файл даже для большого числа строк можно целиком забрать в оперативную память, а практика показала, что работа с ним осуществляется на порядки быстрее, чем любые выборки из базы. Такое решение оказалось возможным в моем случае благодаря тому, что операции обновления таблицы очень редки (перестроение индексного файла -- затратная операция).

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)