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

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

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

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

Вот только не понятно, относительно чего считать похожесть слов. Должен быть некий словарь, с которым сравнивают.
...
Рейтинг: 0 / 0
15.05.2012, 16:25:45
| Ответить | Цитировать | Написать  
Алгоритмы и библиотеки реализующие сравнение строк и текстов на похожесть
    #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:30:58
| Ответить | Цитировать | Написать  
Алгоритмы и библиотеки реализующие сравнение строк и текстов на похожесть
    #37795619
Leonidv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonidv
Участник
И правд непонятно. Даже по первой букве, в общем-то, не выбрать слово. Хэш суммы тоже не посчитать.
http://norvig.com/spell-correct.html - stackoverlfow сюда кинул. Там есть реализация на java.
Сам не разбирался, только ссылку нашел.
...
Рейтинг: 0 / 0
15.05.2012, 16:54:14
| Ответить | Цитировать | Написать  
Алгоритмы и библиотеки реализующие сравнение строк и текстов на похожесть
    #37795697
just_vladimir
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
just_vladimir
Участник
Да думаю не так уж и много, если размерность справочника N, то сначала группируем до уникальных записей, получаем число примерно того же порядка, что и N, ну а дальше сравнение каждый с каждым уже O(n^2), и дальше если у двух групп расстояние меньше заданного, то выполняем коррекцию меньше группы до большей.
...
Рейтинг: 0 / 0
15.05.2012, 17:24:15
| Ответить | Цитировать | Написать  
Алгоритмы и библиотеки реализующие сравнение строк и текстов на похожесть
    #37795706
just_vladimir
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
just_vladimir
Участник
just_vladimirДа думаю не так уж и много, если размерность справочника N, то сначала группируем до уникальных записей, получаем число примерно того же порядка, что и N, ну а дальше сравнение каждый с каждым уже O(n^2), и дальше если у двух групп расстояние меньше заданного, то выполняем коррекцию меньше группы до большей.
предполагаем, что в данных правильных вариантов всё таки больше, чем неправильных :)
...
Рейтинг: 0 / 0
15.05.2012, 17:26:27
| Ответить | Цитировать | Написать  
18 сообщений из 18, страница 1 из 1
Форумы / Java [игнор отключен] [закрыт для гостей] / Алгоритмы и библиотеки реализующие сравнение строк и текстов на похожесть
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=59&msg=37795697&tid=2131794]:
 0ms
get settings:
 19ms
get forum list:
 19ms
check forum access:
 5ms
check topic access:
 5ms
track hit:
 44ms
get topic data:
 20ms
get forum data:
 5ms
get page messages:
 93ms
get tp. blocked users:
 2ms
others: 353ms
total:  565ms
созд. / загр.: 565ms
x
x
Закрыть


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