Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Oracle Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
 Нечёткий поиск слов  [new]
agent5566
Member

Откуда:
Сообщений: 9
Здравствуйте, Ораклоиды!
Прошу совета у знающих людей.
Имеется табличка со словами (одна строка - одно слово), кол-во строк: 10М
Есть задача выполнять нечёткий поиск слов в этой табличке, в принципе в качестве метрики подходит utl_match.jaro_winkler_similarity , есть и свои понаписанные, в общем работает, но с фулл сканом. Проблема в том, что запросы нужно выполнять довольно часто. Встал вопрос о быстродействии, как можно это дело ускорить?

P.S. сейчас запрос выполняется 2-5 мин
24 ноя 12, 09:21    [13522937]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск слов  [new]
Максим Н
Member

Откуда: Екатеринодар
Сообщений: 1439
agent5566,

https://www.sql.ru/forum/actualsearch.aspx?search=%CD%E5%F7%B8%F2%EA%E8%E9+%EF%EE%E8%F1%EA&sin=0&bid=3&a=&ma=0&dt=-1&s=1&so=1
24 ноя 12, 09:27    [13522942]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск слов  [new]
agent5566
Member

Откуда:
Сообщений: 9
Максим Н,

Да, я пользовался поиском. В основном в этих темах люди интересуются самими метриками "похожести" слов, у меня метрика есть подходящая. При вопросах про скорость отсылают к Oracle Text и RCO.
24 ноя 12, 10:23    [13522984]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск слов  [new]
-2-
Member

Откуда:
Сообщений: 15330
agent5566,

какая степень нечеткости допускается в слове на три буквы?
24 ноя 12, 10:25    [13522990]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск слов  [new]
казинак
Member

Откуда:
Сообщений: 1273
agent5566
Здравствуйте, Ораклоиды!
Прошу совета у знающих людей.
Имеется табличка со словами (одна строка - одно слово), кол-во строк: 10М
Есть задача выполнять нечёткий поиск слов в этой табличке, в принципе в качестве метрики подходит utl_match.jaro_winkler_similarity , есть и свои понаписанные, в общем работает, но с фулл сканом. Проблема в том, что запросы нужно выполнять довольно часто. Встал вопрос о быстродействии, как можно это дело ускорить?

P.S. сейчас запрос выполняется 2-5 мин

Я недавно тоже с этим сталкивался, и тоже по форуму рыскал, и ваще по инету. Вывод сделал такой. Индексировать нечеткий поиск низзя. Также как и поиск по Like. Ускорить можно за счет распаралеливания. Если у вас сервак многопоцессорный/многоядерный или кластер, то за счет распаралеливания можно существенно сократить время нечеткого поиска.
24 ноя 12, 10:26    [13522992]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск слов  [new]
agent5566
Member

Откуда:
Сообщений: 9
-2-
agent5566,

какая степень нечеткости допускается в слове на три буквы?

тонко, молодец.






казинак,

ну лайк-то можно проиндексировать, к примеру с помощью Oracle Text
24 ноя 12, 10:33    [13522998]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск слов  [new]
казинак
Member

Откуда:
Сообщений: 1273
agent5566
ну лайк-то можно проиндексировать, к примеру с помощью Oracle Text

Если слова с ошипками пишут, то нифига
24 ноя 12, 10:37    [13523000]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск слов  [new]
-2-
Member

Откуда:
Сообщений: 15330
agent5566
тонко
вопрос вполне утилитарный. можно из строки на входе плодить вариации. время поиска будет - количество вариаций умножить на индексный доступ.
вариант вариций - сортировать уникальные быквы и брать первые шесть кроме первой, второй,.. последней. всего шесть вариаций. шесть поисков по индексу на сортировку уникальных букв хранимых 10М строк будет давать сотни строк к которым уже применять utl_match.

Касаемо oracle text, можно поиграться с индексом ctxrule и аuzzy match. однако у текстового поиска свои представления о нечеткости и могут совсем не совпадать с ожиданиями. кроме того русский текст работает только на utf8 с 11g и имеет ограничения. RCO частично решает этот вопрос.

Оптимальным решение этой задачи делать не на оракле.
24 ноя 12, 10:46    [13523015]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск слов  [new]
agent5566
Member

Откуда:
Сообщений: 9
В общем решил сделать на скорую руку, чтобы как-то работало: перевожу слова в латиницу и юзаю Oracle Text, по CONTEXT индексу выбираю через SOUNDEX. По выбранным словам считаю метрику utl_match.jaro_winkler_similarity.
24 ноя 12, 12:06    [13523160]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск слов  [new]
mayton
Member

Откуда: loopback
Сообщений: 49739
agent5566
Здравствуйте, Ораклоиды!
Прошу совета у знающих людей.
Имеется табличка со словами (одна строка - одно слово), кол-во строк: 10М
Есть задача выполнять нечёткий поиск слов в этой табличке, в принципе в качестве метрики подходит utl_match.jaro_winkler_similarity , есть и свои понаписанные, в общем работает, но с фулл сканом. Проблема в том, что запросы нужно выполнять довольно часто. Встал вопрос о быстродействии, как можно это дело ускорить?

P.S. сейчас запрос выполняется 2-5 мин

Ты определись сначала что такое для тебя - нечёткий поиск и какая
глубина нечёткости тебе нужна. (Чем глубже тем тяжелее будет
искать ибо формулы и метрики сложнее). И хотелось бы тест-кейс
в качестве примера. Ну типа там

Барабан - нечетко похоже на Сарафан и т .д. В теории есть
формула Дамерау-Левинштейна которая меряет насколько 1
слово похоже на другое. Может тебе подойдет. Но это всё
кастомизация...
24 ноя 12, 21:52    [13524322]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск слов  [new]
orawish
Member

Откуда: Гадюкино-2 (City)
Сообщений: 15487
казинак
..
Я недавно тоже с этим сталкивался, и тоже по форуму рыскал, и ваще по инету. Вывод сделал такой. Индексировать нечеткий поиск низзя..

ну, значит плохо рыскали.
можно (и нужно) индексировать нечеткий поиск. иначе - на сколько-нибудь значительных данных, в смысле производительности, шансов нет никаких.
24 ноя 12, 23:35    [13524570]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск слов  [new]
guest_guest
Guest
Напишите свою функцию а-ля Ливенштейн непосредственно под ваши данные.
25 ноя 12, 07:33    [13525026]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск слов  [new]
казинак
Member

Откуда:
Сообщений: 1273
orawish
казинак
..
Я недавно тоже с этим сталкивался, и тоже по форуму рыскал, и ваще по инету. Вывод сделал такой. Индексировать нечеткий поиск низзя..

ну, значит плохо рыскали.
можно (и нужно) индексировать нечеткий поиск. иначе - на сколько-нибудь значительных данных, в смысле производительности, шансов нет никаких.

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

а проблема производительности, за счет распаралеливания вполне нормально решается
25 ноя 12, 09:08    [13525042]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск слов  [new]
agent5566
Member

Откуда:
Сообщений: 9
mayton
agent5566
Здравствуйте, Ораклоиды!
Прошу совета у знающих людей.
Имеется табличка со словами (одна строка - одно слово), кол-во строк: 10М
Есть задача выполнять нечёткий поиск слов в этой табличке, в принципе в качестве метрики подходит utl_match.jaro_winkler_similarity , есть и свои понаписанные, в общем работает, но с фулл сканом. Проблема в том, что запросы нужно выполнять довольно часто. Встал вопрос о быстродействии, как можно это дело ускорить?

P.S. сейчас запрос выполняется 2-5 мин

Ты определись сначала что такое для тебя - нечёткий поиск и какая
глубина нечёткости тебе нужна. (Чем глубже тем тяжелее будет
искать ибо формулы и метрики сложнее). И хотелось бы тест-кейс
в качестве примера. Ну типа там

Барабан - нечетко похоже на Сарафан и т .д. В теории есть
формула Дамерау-Левинштейна которая меряет насколько 1
слово похоже на другое. Может тебе подойдет. Но это всё
кастомизация...

ну так я определился, написал же в теме, что для меня подходит метрика Джаро-Винклера.
25 ноя 12, 18:57    [13525905]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск слов  [new]
orawish
Member

Откуда: Гадюкино-2 (City)
Сообщений: 15487
казинак
orawish
пропущено...

ну, значит плохо рыскали.
можно (и нужно) индексировать нечеткий поиск. иначе - на сколько-нибудь значительных данных, в смысле производительности, шансов нет никаких.

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

а проблема производительности, за счет распаралеливания вполне нормально решается

я жеж говорил - плохо вы искали.
попробуйте поискать по контексту двухфазные
25 ноя 12, 20:55    [13526338]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск слов  [new]
hexcept
Member

Откуда:
Сообщений: 237
фиг знат, почему у тс индексы не рулят, но простейший index full scan на 2-х млн записей дает ~3-4 sec:
-- индекс по fio (ex: 'Иванов И. И.')
select
 fio from <tab> where ( fio like 'А%' or fio like '_лекс%' )
 and utl_match.jaro_winkler_similarity(initcap(fio),'Александров')>70
+можно ж перед метрикой instr/substr/translate задействовать а-ля
and nvl(length(translate(initcap(fio),'*. Александров','*')),0)<3
секунд в 10 уж точно уложить можно
26 ноя 12, 10:18    [13527763]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск слов  [new]
казинак
Member

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

а проблема производительности, за счет распаралеливания вполне нормально решается

я жеж говорил - плохо вы искали.
попробуйте поискать по контексту двухфазные

Ну вот нагуглил
автор
В первой фазе (ETL) производится автоматизированный анализ отдельных документов, структуризация их контента и формирование хранилищ исходной и аналитической информации. Во второй фазе (OLAP, Text Mining, Data Mining) — извлечение в оперативном режиме знаний из хранилища или из полученной по запросу подборки документов

Это то же самое что Oracle Text делает. Но нам всякая рубрикация, семантичекие связи и прочее, просто не нужны были. У нас были короткие строки типа ФИО или Адрес.

Проблема была в том что много строк с ошибками было. Одни ошипки простые, типа опечатки, другие когда вместо ФИО писали ИОФ или ФИ, ну и т.д.
И как можно индексировать всевозможные ошибочные написания?
26 ноя 12, 12:37    [13528692]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск слов  [new]
agent5566
Member

Откуда:
Сообщений: 9
hexcept
фиг знат, почему у тс индексы не рулят, но простейший index full scan на 2-х млн записей дает ~3-4 sec:
-- индекс по fio (ex: 'Иванов И. И.')
select
 fio from <tab> where ( fio like 'А%' or fio like '_лекс%' )
 and utl_match.jaro_winkler_similarity(initcap(fio),'Александров')>70
+можно ж перед метрикой instr/substr/translate задействовать а-ля
and nvl(length(translate(initcap(fio),'*. Александров','*')),0)<3
секунд в 10 уж точно уложить можно


ну вы ввели лайки, я же ищу просто

select
 fio from <tab> where utl_match.jaro_winkler_similarity(field,'text')>70


Очевидно, если ввести предположение о совпадении N-префикса будет юзаться индекс.
26 ноя 12, 13:24    [13529114]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск слов  [new]
dbms_photoshop
Member

Откуда: sqlmdx.net
Сообщений: 5151
agent5566
как можно это дело ускорить?
Domain index. Погугли "fuzzy search domain index oracle".
26 ноя 12, 13:37    [13529217]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск слов  [new]
orawish
Member

Откуда: Гадюкино-2 (City)
Сообщений: 15487
казинак
orawish
пропущено...

я жеж говорил - плохо вы искали.
попробуйте поискать по контексту двухфазные

Ну вот нагуглил
автор
В первой фазе (ETL) производится автоматизированный анализ отдельных документов, структуризация их контента и формирование хранилищ исходной и аналитической информации. Во второй фазе (OLAP, Text Mining, Data Mining) — извлечение в оперативном режиме знаний из хранилища или из полученной по запросу подборки документов

Это то же самое что Oracle Text делает. Но нам всякая рубрикация, семантичекие связи и прочее, просто не нужны были. У нас были короткие строки типа ФИО или Адрес.

Проблема была в том что много строк с ошибками было. Одни ошипки простые, типа опечатки, другие когда вместо ФИО писали ИОФ или ФИ, ну и т.д.
И как можно индексировать всевозможные ошибочные написания?

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

ок. давайте разберёмся. пусть у нас есть 1e6 строк из которых надо найти такие, которые не равны, но с достаточной степенью похожи. какие алгоритмы ту похожесть вычисляют - не так важно. есть utl_match и самим написать нечто можно, но
важно то, что алгоритмы такие относительно дорогие и индексом (сами по себе, в общем случае) не могут быть поддержаны.
что такое сравнение набора 1e6 с самим собой. это 1e6*1e6, ну еще пополам - всё равно много, до опупения.
на ~один раз - ещё куда ни шло (особливо параллельно если ;) , ну а если чаще - нафик, нафик. надо ускоряться.
как? индексировать! что? да почти всё равно что, главное - не надо стремиться построить один индекс.
надо несколько. пример. по теме топика - сравниваем слова.
строим например ~четыре fbi индекса, например, битмэповских
1) substr(s,1,2)
2) substr(s,2,2)
3) substr(s,5,2)
4) substr(s,-2)
теперь запрос. строим юнион от четырех селф-джойнов таблицы, в каждом из которых строго требуем соответствия строк условию
одного из индексов. вот это и есть первая фаза нечёткого поиска. её суть - дёшево подобрать кандидатов для дорогого
сравнения (во второй фазе).
если индексы селективные, то вместо двенадцатого порядка сравнений получается на несколько порядков меньше
26 ноя 12, 20:51    [13532618]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск слов  [new]
казинак
Member

Откуда:
Сообщений: 1273
orawish
ок. давайте разберёмся. пусть у нас есть 1e6 строк из которых надо найти такие, которые не равны, но с достаточной степенью похожи. какие алгоритмы ту похожесть вычисляют - не так важно. есть utl_match и самим написать нечто можно, но
важно то, что алгоритмы такие относительно дорогие и индексом (сами по себе, в общем случае) не могут быть поддержаны.
что такое сравнение набора 1e6 с самим собой. это 1e6*1e6, ну еще пополам - всё равно много, до опупения.
на ~один раз - ещё куда ни шло (особливо параллельно если ;) , ну а если чаще - нафик, нафик. надо ускоряться.
как? индексировать! что? да почти всё равно что, главное - не надо стремиться построить один индекс.
надо несколько. пример. по теме топика - сравниваем слова.
строим например ~четыре fbi индекса, например, битмэповских
1) substr(s,1,2)
2) substr(s,2,2)
3) substr(s,5,2)
4) substr(s,-2)

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

Это то же самое что и биграммный индекс - его мы пробовали.
27 ноя 12, 07:37    [13533745]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск слов  [new]
xymbo
Member

Откуда: Донской --> Москва
Сообщений: 2560
казинак,

А в итоге, как Вы решили задачу? Можно поподробнее объяснить.

Спасибо.
27 ноя 12, 12:37    [13535410]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск слов  [new]
orawish
Member

Откуда: Гадюкино-2 (City)
Сообщений: 15487
казинак
orawish
ок. давайте разберёмся. пусть у нас есть 1e6 строк из которых надо найти такие, которые не равны, но с достаточной степенью похожи. какие алгоритмы ту похожесть вычисляют - не так важно. есть utl_match и самим написать нечто можно, но
важно то, что алгоритмы такие относительно дорогие и индексом (сами по себе, в общем случае) не могут быть поддержаны.
что такое сравнение набора 1e6 с самим собой. это 1e6*1e6, ну еще пополам - всё равно много, до опупения.
на ~один раз - ещё куда ни шло (особливо параллельно если ;) , ну а если чаще - нафик, нафик. надо ускоряться.
как? индексировать! что? да почти всё равно что, главное - не надо стремиться построить один индекс.
надо несколько. пример. по теме топика - сравниваем слова.
строим например ~четыре fbi индекса, например, битмэповских
1) substr(s,1,2)
2) substr(s,2,2)
3) substr(s,5,2)
4) substr(s,-2)

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

Это то же самое что и биграммный индекс - его мы пробовали.

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

то надо думать и учиться копать
27 ноя 12, 12:53    [13535536]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск слов  [new]
казинак
Member

Откуда:
Сообщений: 1273
xymbo
казинак,

А в итоге, как Вы решили задачу? Можно поподробнее объяснить.

Спасибо.

Мы кстати пробовали еще способ Кайта : Create Table t as select rowid,fio||address from t1, закрепить эту табличку в кэше и потом нечеткий поиск по ней, но на экзадате это большого выигрыша не дало.

Потому просто разбили табличку по которой искали (где-то 20 млн записей) на 24 диапазона (ядер было 48) и запускали 24 паралельных джоба. Фулскан с жаровинклером был за где-то три минуты, а паралельно около 6 секунд. Нам хватило.
27 ноя 12, 15:35    [13537292]     Ответить | Цитировать Сообщить модератору
 Re: Нечёткий поиск слов  [new]
казинак
Member

Откуда:
Сообщений: 1273
orawish
казинак
пропущено...

Это то же самое что и биграммный индекс - его мы пробовали.

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

то надо думать и учиться копать

даже отвечать неохото
27 ноя 12, 15:37    [13537300]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
Все форумы / Oracle Ответить