ReSQL.ru
     
powered by simpleCommunicator - 2.0.51     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Разработка информационных систем [игнор отключен] [закрыт для гостей] / Интересная задача по поиску похожих слов
20 сообщений из 20, страница 1 из 1
Интересная задача по поиску похожих слов
    #35532240
Святогор
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Святогор
Гость
Имеем функцию, которая просчитывает Расстояние Левенштейна для слова из английского языка.

Есть таблица в SQL базе данных, в которой содержится 1000 000 (миллион) слов английского языка (хороший такой словарь).

Задача: для слова X найти множество, до которых расстояние Левенштейна равно L (например L = 3).

Другими словами, надо найти список слов похожих на X. Например, для слова community он будет выглядеть примерно так: cammunity, comunity, communiti et cetera.

Нет, можно конечно сделать перебором, но тогда мы получим результат лишь через пол-часа ;-)
...
Рейтинг: 0 / 0
10.09.2008, 15:44
| Ответить | Цитировать | Написать  
Интересная задача по поиску похожих слов
    #35532343
Фотография Александр Гoлдун
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Александр Гoлдун
Участник
Если искомое слово произвольно, то подозреваю, что кроме перебора никак.

P.S. Это случайно не родственная тема:
Как бороться с дубликатами в справочниках
?
...
Рейтинг: 0 / 0
10.09.2008, 16:14
| Ответить | Цитировать | Написать  
Интересная задача по поиску похожих слов
    #35532364
Святогор
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Святогор
Гость
Александр ГoлдунЕсли искомое слово произвольно, то подозреваю, что кроме перебора никак.


Думаю, что это плохой ответ. Можно, например, как-нибудь подготовить БД, к примеру для каждого слова прописать метрику, которая вычисляется по некой оценочной функции. А потом загружать только те слова, у которых метрика похожа на метрику исходно слова. Вопрос в том, как выбрать эту оценочную функцию...
...
Рейтинг: 0 / 0
10.09.2008, 16:19
| Ответить | Цитировать | Написать  
Интересная задача по поиску похожих слов
    #35532391
Фотография Александр Гoлдун
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Александр Гoлдун
Участник
Святогор
Думаю, что это плохой ответ. Можно, например, как-нибудь подготовить БД, к примеру для каждого слова прописать метрику, которая вычисляется по некой оценочной функции.
Какую метрику для сравнения с произвольным словом можно прописать? Универсальная метрика здесь только одна: это само слово, нравится вам это или нет. Хотя может быть есть возможность слегка оптимизировать это, если к примеру использовать тот факт, что тут не просто случайные наборы букв, а именно слова какого-то языка. Но и тут у меня мысль не идет дальше возможности использовать что-то типа сжатия по словарю. Ибо упирается все в то, что я не представляю как использовать такое для определения расстояния, кроме как развернув в полное слово.

Или у вас есть решение этой проблемы?
...
Рейтинг: 0 / 0
10.09.2008, 16:27
| Ответить | Цитировать | Написать  
Интересная задача по поиску похожих слов
    #35532473
Kachalov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kachalov
Участник
СвятогорДругими словами, надо найти список слов похожих на X. Например, для слова community он будет выглядеть примерно так: cammunity, comunity, communiti et cetera.

Нет, можно конечно сделать перебором, но тогда мы получим результат лишь через пол-часа ;-)

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

[a-z]{0,2}ammunity
c[a-z]{0,2}mmunity
ca[a-z]{0,2}munity
...

количество запросов будет равно количеству символов в исходном слове (можно и в один запрос исхитриться впихнуть), а уже в полученной коллекции вести сравнение с помощью расстояния Левенштейна.

Прошу не чухонить - это всего лишь предположение выдвинутое без какого-либо обдумывания :)
...
Рейтинг: 0 / 0
10.09.2008, 16:50
| Ответить | Цитировать | Написать  
Интересная задача по поиску похожих слов
    #35532710
SeVa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SeVa
Участник
Для общего случая подобная метрика не подходит.
...
Рейтинг: 0 / 0
10.09.2008, 18:12
| Ответить | Цитировать | Написать  
Интересная задача по поиску похожих слов
    #35532781
Kachalov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kachalov
Участник
SeVaДля общего случая подобная метрика не подходит.
- а Вы обсуждаете конкретную задачу или Вас интересует "сферический конь в вакууме"? Для конкретных задач есть конкретные решения, например: MySQL+levenshtein
...
Рейтинг: 0 / 0
10.09.2008, 18:53
| Ответить | Цитировать | Написать  
Интересная задача по поиску похожих слов
    #35532792
Kachalov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kachalov
Участник
СвятогорНет, можно конечно сделать перебором, но тогда мы получим результат лишь через пол-часа ;-)
- в общем случае попробуйте использовать самодельную хранимую процедуру и запихните ее в в секцию "WHERE ..." - сколько это займет времени, в "общем случае" неизвестно :)
...
Рейтинг: 0 / 0
10.09.2008, 18:58
| Ответить | Цитировать | Написать  
Интересная задача по поиску похожих слов
    #35532832
Bely
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bely
Участник
СвятогорНет, можно конечно сделать перебором, но тогда мы получим результат лишь через пол-часа ;-)Когда некоторое время назад интересовался нечетким поиском, то натолкнулся на следующую научную статью, которую сейчас не нашел.

Смысл там был указан следующий:
Для сравнения слов там использовался вектор, с кол-вом координат, равным кол-ву символов в алфавите.
т.е. для Русского языка - это будет 33 мерный вектор.
Каждой позиции в векторе - сопоставляем букву алфавита (можно по порядку, для простоты)

Каждому слову сопоставляем вектор, у которого в соответствующей позиции стоит 0 - если такой буквы нет в этом слове и 1 - если такая буква есть в таком слове.

Данный вектор можно использовать в качесстве хэш функции.

Теперь, чтобы найти "похожие слова", надо просто из вектора слова сгенерить "вектора похожих слов".
Далее - по полученному списку векторов - находим все похожие слова в вашей таблице и для этих пар уже можно запускать процедуру определения расстояния Левинштэйна.
...
Рейтинг: 0 / 0
10.09.2008, 19:30
| Ответить | Цитировать | Написать  
Интересная задача по поиску похожих слов
    #35532841
Bely
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bely
Участник
Кстати, нашел статью .
В ней вектор называется сигнатурой.
...
Рейтинг: 0 / 0
10.09.2008, 19:36
| Ответить | Цитировать | Написать  
Интересная задача по поиску похожих слов
    #35532847
Bely
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bely
Участник
BelyТеперь, чтобы найти "похожие слова", надо просто из вектора слова сгенерить "вектора похожих слов".
Далее - по полученному списку векторов - находим все похожие слова в вашей таблице и для этих пар уже можно запускать процедуру определения расстояния Левинштэйна.До кучи - в качестве одного из параметров для отсечения можно использовать еще длинну слова.
Если мы ищем дистанцию редактировани не более 1, то имеет смысл сравнивать слова не длиннее/короче чем на один символ.

ну и продумать прочие логические ограничения, которые могут наложиться, если использовать несколько параметров одновременно (длинну, сигнатуру, дистанцию редактирования итп.)
...
Рейтинг: 0 / 0
10.09.2008, 19:42
| Ответить | Цитировать | Написать  
Интересная задача по поиску похожих слов
    #35532860
Kachalov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kachalov
Участник
BelyКстати, нашел статью .
В ней вектор называется сигнатурой.
- тоже когда-то аналогичную конструкцию хотел использовать, но руки не дошли :)
...
Рейтинг: 0 / 0
10.09.2008, 19:58
| Ответить | Цитировать | Написать  
Интересная задача по поиску похожих слов
    #35534060
SeVa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SeVa
Участник
авторДо кучи - в качестве одного из параметров для отсечения можно использовать еще длинну слова.
Если мы ищем дистанцию редактировани не более 1, то имеет смысл сравнивать слова не длиннее/короче чем на один символ.

У Левенштейна есть де ц кая болезнь, не говоря уже о "ООО Рога и Копыта" и "Рога и Копыта ООО"(это не одно слово,но зачастую нужны и такие проверки).
Для нечеткого поиска в БД больше подходит алгоритм q-grams.Я его применял для поиска в товаров в прайслистах конкурентов.
...
Рейтинг: 0 / 0
11.09.2008, 13:57
| Ответить | Цитировать | Написать  
Интересная задача по поиску похожих слов
    #35537439
Чорный Бада
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Чорный Бада
Участник
Загрузите всю таблицу в память. Сейчас проверил ради любопытства - у меня перебор по массиву в 1 млн. слов из 12 букв каждое занял около 11 сек. Intel Core Duo 1.60 GHz, 2 Gb RAM, Windows Vista Business 32, .NET Framework 3.5 SP1.
...
Рейтинг: 0 / 0
13.09.2008, 01:29
| Ответить | Цитировать | Написать  
Интересная задача по поиску похожих слов
    #35539277
AlexTheRaven
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AlexTheRaven
Участник
СвятогорИмеем функцию, которая просчитывает Расстояние Левенштейна для слова из английского языка.
Цель - определить техническую похожесть слова (хлеб - хлев - блеф) или семантическую похожесть (хлеб-булка-каравай)? С семантической похожестью расстояние Левенштейна совсем никак не работает - нужны словари синонимов и/или семантические сети.

Святогор
Есть таблица в SQL базе данных, в которой содержится 1000 000 (миллион) слов английского языка (хороший такой словарь).
Реально используется не более 30'000 слов. Реальная система - всегда компромисс.

Святогор
Задача: для слова X найти множество, до которых расстояние Левенштейна равно L (например L = 3).
IMHO только перебор. Максимум - можно сделать его для известных значений заранее, построив "конкордансы".

Святогор
Другими словами, надо найти список слов похожих на X. Например, для слова community он будет выглядеть примерно так: cammunity, comunity, communiti et cetera.
См. aspell, функцию поиска всех возможных ошибочных слов для правильного. Что правда - не Левенштейн, есть 3 градации, в зависимости от режимов работы aspell.

Святогор
Нет, можно конечно сделать перебором, но тогда мы получим результат лишь через пол-часа ;-)
Для 30'000 вместо 1'000'000 - 1 мин. Для 30'000 слов - 20 дней на построение "конкордансов" по одному значению расстояния Левенштейна. Задача отлично распараллеливается.
...
Рейтинг: 0 / 0
15.09.2008, 12:24
| Ответить | Цитировать | Написать  
Интересная задача по поиску похожих слов
    #35547427
Фотография Нахлобуч
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Нахлобуч
Участник
Soundex?
...
Рейтинг: 0 / 0
18.09.2008, 18:49
| Ответить | Цитировать | Написать  
Интересная задача по поиску похожих слов
    #35547430
Фотография Нахлобуч
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Нахлобуч
Участник
НахлобучSoundex?
...и вообще фонетические алгоритмы.
...
Рейтинг: 0 / 0
18.09.2008, 18:49
| Ответить | Цитировать | Написать  
Интересная задача по поиску похожих слов
    #35547487
SeVa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SeVa
Участник
Попробуй
Код: plaintext
1.
2.
select Soundex('nahl0buch'),Soundex('nahlobuch')
select Soundex('0lga'),Soundex('Olga')
...
Рейтинг: 0 / 0
18.09.2008, 19:26
| Ответить | Цитировать | Написать  
Интересная задача по поиску похожих слов
    #35547489
Фотография Нахлобуч
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Нахлобуч
Участник
На саундексе свет клином не сошелся.
...
Рейтинг: 0 / 0
18.09.2008, 19:29
| Ответить | Цитировать | Написать  
Интересная задача по поиску похожих слов
    #35547494
SeVa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SeVa
Участник
Неплохой обзор возможных алгоритмов Информационный поиск
Есть и сравнительный анализ быстродействия
...
Рейтинг: 0 / 0
18.09.2008, 19:36
| Ответить | Цитировать | Написать  
20 сообщений из 20, страница 1 из 1
Форумы / Разработка информационных систем [игнор отключен] [закрыт для гостей] / Интересная задача по поиску похожих слов
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=33&msg=35537439&tid=1548701]:
 0ms
get settings:
 10ms
get forum list:
 15ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 211ms
get topic data:
 10ms
get forum data:
 3ms
get page messages:
 49ms
get tp. blocked users:
 1ms
others: 301ms
total:  606ms
созд. / загр.: 606ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]