sirs: "Искать по совпадению символов - очень плохой вариант, если честно, проблемы со скоростью и памятью гарантированы. Тем более могут быть слова с идентичным массивом символов, но разным порядком следования. "
- полностью согласен. Если я не разберусь с более умными вариантами, не останется ничего другого :) Благо объемы не очень большие.
"Артур: Смотрите, в любой случае на входе мы ждем строку, а на выходе - список программ с похожими названиями, я верно считаю? или условие - вернуть одну максимально похожую программу?"
- по-хорошему, на выходе я жду либо фразу "Такой программы нет в справочнике", максимально похожую.
я размышлял примерно так:
В справочнике у меня есть список слов, полученный из строк эталонов. Каждое из этих слов ссылается на оригинальную строку.
Допустим я разбил пользовательский запрос на слова и сравниваю со словами справочника. Тот факт, что я в строке пользователя нахожу слово из справочника уже дает мне намек на то, что запрос есть в базе. Слова "без особого смысла", такие как "программка для документов" не будут давать результата, остается совпадение по "Программуля". Считать пользовательскую строку похожей.
Может разным словам, которые точно имеют смысл, типа "Программуля" дать в справочнике рейтинг выше...
sirs: Я, наверное, погорячился сказав "База". Это будет текстовый документ, который я могу пропарсить и прочесть из него строки.
Тот вопрос " Как определить похожесть двух строк?" как раз мой :)
Там люди дали хорошие ответы, указали на Lucene. Только боюсь это сейчас слишком мощно для меня.
Изучая ответы набрел на тему, где говорили про поиск в индексе словаря, но не объясняли как это делается.
Тут у меня и возникла идея, сделать "самопальный" алгоритм, параллельно разбираясь с Lucene.
Я разобрался с тем, как сделать приемлемое сравнение слов на похожесть с учетом количества ошибок. Не понимаю как искать похожесть целых предложений. Просто проверка " пусть если равны 2 слова в каждом, то считать похожими" как-то не подходит на мой взгляд.
Как-то так я это и представлял. Даже почти решил проблему "похожести" слов через тупое сравнение на совпадение символов ( коряво, но какие-то результаты даст. Программуля == програмуля).
А вот вопрос. Когда я получу по ключевому слову из строки список эталонных названий, я перейду к поиску по второму слову. Этот поиск даст мне еще список строк, в которых встречается "слово keywords".
А как быть дальше? Проверить на совпадение во всех случаях ( или на какой-то процент совпадений)?
sirs: я бы хотел найти все строки в базе наиболее ПОХОЖИЕ на пользовательский запрос. В строке пользователя в любом случае есть слово "Программуля" ( орфографические ошибки в расчет не берем).
То есть будут совпадения с исходной строкой. Проблема в том, что может быть совпадение точное, а может и одно слово совпасть, но как раз то самое "Программуля".
Также упрощает тот факт, что пользователь хоть и будет ошибаться, или писать лишние слова, но в каких-то разумных пределах.
У меня сейчас уровень владения Java : достать из файла строки, прогнать циклом, разбить на слова, запихнуть в HashMap, прочесть файл, открыть файл. Что-то типа Junior.
Сейчас важнее скорость разработки, и, пожалуй, не 100% точность поиска с возможностью допилить попозже.
В идеале цель такова, чтобы поиск дал понять, есть такая строка в справочнике, или нет. Быть может, добавить участие оператора в процесс подтверждения "верно\неверно".
Алгоритмами владею весьма скудно. То есть в математических раскладах сейчас сходу не разберусь.
Walt Disney: Вот оно что. :) Спасибо большое за ответ.
Теперь пойду разбираться с библиотекой. В любом случае любопытно как делается индексация списка строк ( для личного развития), и понять как потом в индексируемом словаре осуществляется поиск.
Но это уже тема отдельного вопроса.
Walt Disney: Спасибо за комментарий и за названия библиотек. И правда начинаю закапываться вглубь, хотя сейчас это не требуется. ( чем глубже, тем страшней).
[У вас же два списка, поэтому вам в любом случае брать один элемент из первого списка и сравнивать (т.е. искать наиболее похожие)] - в данном случае возникает вопрос похожести. Тут я уже либо пользуюсь некими алгоритмами расстояния, либо пилю свой способ на свое усмотрение. Так получается?
Спасибо за комментарий. Я правильно понял, что я беру строку, беру некий список и сортирую его так, чтобы "вверху" списка были наиболее похожие строки? Или делаю новый список со ссылками настроки из списка-словаря. Так?
А насчет индексации. Видел некоторые пояснения на хабре о том, как делается индекстиз списка строк. Не совсем понятно каким образом этот индекс участвует в поиске и ранжировании? Могли бы пояснить или указать на источник с информацией?
Владимир, спасибо за ответ. Я так понимаю, что алгоритм нечеткого сравнения идет для слов, а как быть для строки? Выдумать свой собственный алгоритм (читай велосипед) на основе полученных данных о словах?
- полностью согласен. Если я не разберусь с более умными вариантами, не останется ничего другого :) Благо объемы не очень большие.
"Артур: Смотрите, в любой случае на входе мы ждем строку, а на выходе - список программ с похожими названиями, я верно считаю? или условие - вернуть одну максимально похожую программу?"
- по-хорошему, на выходе я жду либо фразу "Такой программы нет в справочнике", максимально похожую.