Дополнительная проблема в том что строка для поиска составная, т.е. в одной позиции буквы может быть больше одного символа,
нужно найти максимально длинное общее совпадение, например:
dATIS
thimATIS : найдено совпадение 4-рех символов
На текущий момент найдено решение, которое позволяет найти совпадения примерно за O(nm) времени , это не устраивает, т.к. в реальном применении база эталонных строк будет в районе 4 млн. записей, каждая запись ~50 символов, количество сложных строк для поиска 4-6 тыс на запрос (длинна 150 символов),
плюс дополнительная обработка каждого результата поиска тестовой строки, итого оценка требуемых операций несколько десятков террафлопс...
Нужно найти линейный алгоритм поика, может кто-нибудь знает, в каком направлении копать?
Re: найти нечеткие совпадения строки в массиве строк
Здравствуйте, deng, Вы писали: D>Нужно найти линейный алгоритм поика, может кто-нибудь знает, в каком направлении копать?
я такой делал. сделать можно. коммерческая тайна. хе-хе.
Re[2]: найти нечеткие совпадения строки в массиве строк
Здравствуйте, __kot2, Вы писали:
__>я такой делал. сделать можно. коммерческая тайна. хе-хе.
Хотя бы что-то можешь подсказать? Пример где можно посмотреть работу алгоритма, какая литература есть по теме? Общий способ какой, на основе суффиксных деревьев? В примерах поиска ,какие нашел, везде фиксированная тестовая строка для поиска в дереве, как прикрутить строку у которой может быть несколько вариантов одного символа даже представить боюсь :/
Re[3]: найти нечеткие совпадения строки в массиве строк
Здравствуйте, deng, Вы писали: D>Хотя бы что-то можешь подсказать? Пример где можно посмотреть работу алгоритма, какая литература есть по теме? Общий способ какой, на основе суффиксных деревьев? В примерах поиска ,какие нашел, везде фиксированная тестовая строка для поиска в дереве, как прикрутить строку у которой может быть несколько вариантов одного символа даже представить боюсь :/
нет. никаких деревьев. хотя в вашем конкретном случае они могут и пригодиться
общий смысл в что чтобы получить нечеткое совпадение нужно все равно иметь какое-то четкое. то есть нечеткое это несколько четких
Re: найти нечеткие совпадения строки в массиве строк
Здравствуйте, deng, Вы писали:
D>Возникла задача ускорить поиск совпадений сложной строки в массиве строк.
Как вариант, гуглим расстояние Левенштейна.
Для СУБД может оказаться удобнее хранить в вычисляемом столбце что-то аля SOUNDEX (гуглим %servername% fuzzy match, для sql server-а — см тынц). На крайний случай можно посмотреть готовые средства для полнотекстового поиска.
Re[4]: найти нечеткие совпадения строки в массиве строк
Здравствуйте, __kot2, Вы писали:
__>нет. никаких деревьев. хотя в вашем конкретном случае они могут и пригодиться __>общий смысл в что чтобы получить нечеткое совпадение нужно все равно иметь какое-то четкое. то есть нечеткое это несколько четких
Для моего случая не подойдет, т.к. в строке поиска для каждой буквы может быть до 20 значений, длинна слова 144 буквы, количество четких вариантов получается слишком большое. Слово для поиска получается как массив, в каждой позиции которого список букв, жуть )
Здравствуйте, Sinix, Вы писали:
__>Как вариант, гуглим расстояние Левенштейна.
По расстоянию Левенштейна смотрел, для него есть готовые алгоритмы , но кроме замены буквы еще учитываются удаления и вставки, которые не требуются для моей задачи, интересно, получиться ли переделать алгоритмы, чтобы вычислялись только замены букв? И еще, для случая поиска слова в котором находятся метасимволы опять же не попадались способы.
Re[5]: найти нечеткие совпадения строки в массиве строк
Здравствуйте, deng, Вы писали: D>Для моего случая не подойдет, т.к. в строке поиска для каждой буквы может быть до 20 значений, длинна слова 144 буквы, количество четких вариантов получается слишком большое. Слово для поиска получается как массив, в каждой позиции которого список букв, жуть )
подойдет-подойдет. не в лоб конечно
Re[6]: найти нечеткие совпадения строки в массиве строк
Здравствуйте, __kot2, Вы писали:
__>подойдет-подойдет. не в лоб конечно
N-граммы? С ними тоже возникает проблема: должны быть общие участки размером в N-грамму, если общие участки нужного размера не попадаются, будут пропускаються правильные варианты совпадений, это очень не желательно.
типа:
слово для поиска: маха, набор триграм: мах, аха
слова базы : маша, мыха, миха
в результате ничего не отыщется, хотя при точном поиске должо быть
МАхА
МАшА
МаХА
МыХА
МаХА
МиХА
Как вариант можно составлять N-граммы с пропусками позиций,причем в разных вариантах,(типа маха (м-ха)) но все равно пропусков правильных результатов не избежать, все сочетания все равно не учтешь.
Хотелось бы найти решение для точного поиска общих частей, прежде чем приступать к реализации поиска N-грамм, или хотя бы убедиться что такого нет )
Re: найти нечеткие совпадения строки в массиве строк
Здравствуйте, deng, Вы писали:
D>Доброго дня! D>Возникла задача ускорить поиск совпадений сложной строки в массиве строк.
Построй трай и ходи по нему. Только делай переходы по несовпадающим символам, накапливая для состояний количество ошибок. Скажем, есть слова:
test и meso
строим трай:
--> 0 -- t --> 1 -- e -- > 2 -- s --> 3 -- t --> 4*
\ -- m --> 5 -- e --> 6 -- s --> 7 -- o --> 8*
и на вход приходит mest. Идем по трайю. Переходим сразу в два состояния: {1, 2}, причем состоние 1 с коэффициентом 1. Идем дальше по состояниям. Доходим до состояния 4 с коэффициентом 1, который наследуется, и до состояния 8, также с коэффициентом 1, который получился при переходе из состояния 7. Алгоритм линейный от длины входной строки, но если трай ветвистый, то вариантов будет до фига и множество состояний при переходах будет большое. Чудес не бывает, здесь задача по любому имеет большую вычислительную сложность.
Re[7]: найти нечеткие совпадения строки в массиве строк
D>N-граммы? С ними тоже возникает проблема: должны быть общие участки размером в N-грамму, если общие участки нужного размера не попадаются, будут пропускаються правильные варианты совпадений, это очень не желательно.
можно пределиться каков минимальный размер совпадений, исходя из размеров словаря и использовать его в качестве размера N-граммы. В твоем случае 50 для базовых строк, 150 для запроса, врядли имеет смысл брать меньше, чем 10-граммы.
Re: найти нечеткие совпадения строки в массиве строк
