Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Java [игнор отключен] [закрыт для гостей] / Алгоритмы и библиотеки реализующие сравнение строк и текстов на похожесть / 18 сообщений из 18, страница 1 из 1
14.05.2012, 14:01:53
    #37793194
just_vladimir
just_vladimir
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмы и библиотеки реализующие сравнение строк и текстов на похожесть
Всем доброго времени суток!
Подскажите, какие существуют известные алгоритмы (возможно их реализации на Java) выполняющие проверку строк на похожесть? Или выявлять опечатки?
Вообще исходная задача примерно следующая, есть некий набор данных, которые надо себе загружать, при этом известно, что некоторые поля, которые явно являются справочными (и его нужно вести) вводятся пользователями в ручную, как следствие в них могут быть опечатки, которые хотелось бы выявлять и бороться с ними.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.05.2012, 14:22:52
    #37793238
Blazkowicz
Blazkowicz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмы и библиотеки реализующие сравнение строк и текстов на похожесть
Так сравнивать надо текст, или таки отдельные слова? Если слова, то вроде просто. Словарь, отсортировать по частоте. И по нему искать. Без ошибок. Потом с одной ошибкой. И т.д.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.05.2012, 14:23:44
    #37793241
Leonidv
Leonidv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмы и библиотеки реализующие сравнение строк и текстов на похожесть
just_vladimir,

lucene смотрите.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.05.2012, 14:33:52
    #37793262
just_vladimir
just_vladimir
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмы и библиотеки реализующие сравнение строк и текстов на похожесть
BlazkowiczТак сравнивать надо текст, или таки отдельные слова? Если слова, то вроде просто. Словарь, отсортировать по частоте. И по нему искать. Без ошибок. Потом с одной ошибкой. И т.д.
Обычно слова, словосочетания, ограничение сверху не более чем предложение.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.05.2012, 14:37:38
    #37793269
just_vladimir
just_vladimir
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмы и библиотеки реализующие сравнение строк и текстов на похожесть
Leonidvjust_vladimir,

lucene смотрите.
Вроде как не совсем то, чего бы хотелось.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.05.2012, 14:42:27
    #37793278
just_vladimir
just_vladimir
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмы и библиотеки реализующие сравнение строк и текстов на похожесть
А вообще что то подобное видимо нужно http://en.wikipedia.org/wiki/Levenshtein_distance
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.05.2012, 14:45:53
    #37793283
Nixic
Nixic
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмы и библиотеки реализующие сравнение строк и текстов на похожесть
just_vladimirА вообще что то подобное видимо нужно http://en.wikipedia.org/wiki/Levenshtein_distance
Да-да-да.. сидел щас вот мучительно вспоминал название, спасибо что облегчили мою участь )))
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.05.2012, 15:10:32
    #37793345
Leonidv
Leonidv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмы и библиотеки реализующие сравнение строк и текстов на похожесть
just_vladimirLeonidvjust_vladimir,

lucene смотрите.
Вроде как не совсем то, чего бы хотелось.
Если правильно использовать, будет.
http://wiki.apache.org/lucene-java/SpellChecker
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.05.2012, 15:14:52
    #37793356
Leonidv
Leonidv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмы и библиотеки реализующие сравнение строк и текстов на похожесть
Еще должна быть связка между java и стандартными линуксовыми spell checker'ами. Можно через Eclipse на нее выйти.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.05.2012, 15:23:35
    #37793370
just_vladimir
just_vladimir
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмы и библиотеки реализующие сравнение строк и текстов на похожесть
Leonidv,
спасибо, за подсказки и за нужную часть от lucene, буду копать и в этих направлениях.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.05.2012, 15:35:15
    #37793399
Leonidv
Leonidv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмы и библиотеки реализующие сравнение строк и текстов на похожесть
http://stackoverflow.com/questions/559510/looking-for-java-spell-checker-library - посмотрите еще здесь.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.05.2012, 18:30:06
    #37793697
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмы и библиотеки реализующие сравнение строк и текстов на похожесть
just_vladimir, ищи функцию "Расстояние Дамерау-Левинштейна".
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.05.2012, 16:02:55
    #37795457
Joe R
Joe R
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмы и библиотеки реализующие сравнение строк и текстов на похожесть
Библиотека Apache coommons-lang, класс StringUtils, там есть LevenshteinDistance и др.
Также в commons-codec есть классы для фонетики (но вроде как для английского).
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.05.2012, 16:25:45
    #37795534
Leonidv
Leonidv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмы и библиотеки реализующие сравнение строк и текстов на похожесть
Joe R,

Вот только не понятно, относительно чего считать похожесть слов. Должен быть некий словарь, с которым сравнивают.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.05.2012, 16:30:58
    #37795557
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмы и библиотеки реализующие сравнение строк и текстов на похожесть
Да. Дороговато выходит. Сравнивать всё-со-всем.

Код: java
1.
2.
3.
System.out.println(StringUtils.getLevenshteinDistance("Aklin", "mayton"));
System.out.println(StringUtils.getLevenshteinDistance("Aklin", "Alkin"));
System.out.println(StringUtils.getLevenshteinDistance("Aklin", "Leonidv"));



Код: java
1.
2.
3.
5
2
6


Наверное должен быть какой-то индекс универсального справочника.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.05.2012, 16:54:14
    #37795619
Leonidv
Leonidv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмы и библиотеки реализующие сравнение строк и текстов на похожесть
И правд непонятно. Даже по первой букве, в общем-то, не выбрать слово. Хэш суммы тоже не посчитать.
http://norvig.com/spell-correct.html - stackoverlfow сюда кинул. Там есть реализация на java.
Сам не разбирался, только ссылку нашел.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.05.2012, 17:24:15
    #37795697
just_vladimir
just_vladimir
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмы и библиотеки реализующие сравнение строк и текстов на похожесть
Да думаю не так уж и много, если размерность справочника N, то сначала группируем до уникальных записей, получаем число примерно того же порядка, что и N, ну а дальше сравнение каждый с каждым уже O(n^2), и дальше если у двух групп расстояние меньше заданного, то выполняем коррекцию меньше группы до большей.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.05.2012, 17:26:27
    #37795706
just_vladimir
just_vladimir
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмы и библиотеки реализующие сравнение строк и текстов на похожесть
just_vladimirДа думаю не так уж и много, если размерность справочника N, то сначала группируем до уникальных записей, получаем число примерно того же порядка, что и N, ну а дальше сравнение каждый с каждым уже O(n^2), и дальше если у двух групп расстояние меньше заданного, то выполняем коррекцию меньше группы до большей.
предполагаем, что в данных правильных вариантов всё таки больше, чем неправильных :)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Java [игнор отключен] [закрыт для гостей] / Алгоритмы и библиотеки реализующие сравнение строк и текстов на похожесть / 18 сообщений из 18, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 571ms
Закрыть
start [/forum/topic.php?fid=59&tablet=1&tid=2131794]:
 0ms
get settings:
 21ms
get forum list:
 21ms
check forum access:
 6ms
check topic access:
 6ms
track hit:
 51ms
get topic data:
 17ms
get forum data:
 4ms
get page messages:
 97ms
get tp. blocked users:
 2ms
others: 346ms
total:  571ms
x
x
Закрыть


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