Как сделать индекс по заданному тексту, и как по этому индексу потом искать?

Question

[Артур]

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

Есть задача:
-имеется список правильных названий программ ( а-ля шаблон, образец, эталон). Названия состоят из 1-6 слов
-имеется список названий программ, которые писали сотрудники. Сотрудники писали не по шаблону, допускали ошибки в написании самих слов, называли программы как-то иначе. При этом все равно сохранялась суть названия.
Например:
эталон "Программуля плюс"
сотрудник написал "Программа для документов Программуля"
Как видно, есть много лишнего, но суть сохранена.

Хочу создать индекс из справочника эталонных названий и как-то в этом индексе искать соответствия с пользовательским запросом ( либо есть совпадение, либо пользовательской программы в словаре нет).
Предполагаю, что ищем по отдельным словам исходные строки и ищем пересечения совпадений. Или не так?

Прошу подсказать как создается индекс, и как по этому индексу производится поиск (алгоритм).
Предметной базой сильно не владею, поэтому прошу объяснить простыми словами.
Писать буду на языке Java.

Спасибо за ответы :)

UPD:
Хочу поделиться с вами тем, как я сделал индекс.
Мне помогли ваши ответы и комментарии.

1. взял строку. строка была вида original_Name : alternate_name_1, alternate_name_2
   
2. запомнил оригинальное имя в отдельную переменную origName.
   
3. очистил ее от мусора. Сюда входило удаление знаков пунктуации, там где у меня в строке были ссылки я сохранял тире "-". Убрал "стоп" слова. Стоп слова я выбрал посредством наблюдений в имеющемся словаре. Выбросил все слова, помимо предлогов и союзов, которые не носили смысловой нагрузки. У меня это были слова типа "портал", "online", общие аббревиатуры "ас", "абс".
   
4. разбил строку на ключевые слова. Всю строку, включая и оригинальное название.
   
5. сохранил в HashMap связку keyWord : origName. Где-то это называли метод обратных ссылок.
   
6. если ключевые слова повторялись, то дописывал к origName другие слова в строку.
   

В получившемся "справочнике" я искал вхождения ключевых слов из запроса. На выходе получал список со всем найденными origName.
Ранжирование заключалось в том, что я считал наибольшее количество совпадений и считал эти совпадения результатом. Иногда было несколько совпадений с одинаковым количеством вхождений. Совпадения были похожими по смыслу, но вносили некую путаницу. (Эту проблему я решил диалоговым окном с "оператором" программы)

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

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

Хочу сказать спасибо тем, кто откликнулся на мои вопросы и дал комментарии.
Это

• sirs @sirs
  
• xmoonlight @xmoonlight
  
• Walt Disney @ruFelix
  

Comments

[sirs]

Ответ зависит от того, насколько вы владеете java, алгоритмами и сколько у вас времени для решения задачи.
Уточните что для вас в приоритете: скорость разработки или точность поиска по справочнику?

[sirs]

Еще одно уточнение: Допустим у вас эталон "Программуля плюс", сотрудник сделал что-то похожее типа "Программа для документов Программуля". Вы хотите найти все созданные сотрудником названия, СОДЕРЖАЩИЕ слово "Программуля" или слово "плюс" или вы хотите найти все названия ПОХОЖИЕ на слово "Программуля" или слово "плюс" ? Это очень важно для выбора алгоритма реализации.
Если вас интересуют "похожие" названия, то можно посмотреть ответы на вопрос Как определить похожесть двух строк?, если же вы ищете только совпадения слов в предложении, то я думаю можно обойтись без сложных алгоритмов.

[Артур]

sirs: Спасибо за ответ.

У меня сейчас уровень владения Java : достать из файла строки, прогнать циклом, разбить на слова, запихнуть в HashMap, прочесть файл, открыть файл. Что-то типа Junior.

Сейчас важнее скорость разработки, и, пожалуй, не 100% точность поиска с возможностью допилить попозже.
В идеале цель такова, чтобы поиск дал понять, есть такая строка в справочнике, или нет. Быть может, добавить участие оператора в процесс подтверждения "верно\неверно".

Алгоритмами владею весьма скудно. То есть в математических раскладах сейчас сходу не разберусь.

[Артур]

sirs: я бы хотел найти все строки в базе наиболее ПОХОЖИЕ на пользовательский запрос. В строке пользователя в любом случае есть слово "Программуля" ( орфографические ошибки в расчет не берем).
То есть будут совпадения с исходной строкой. Проблема в том, что может быть совпадение точное, а может и одно слово совпасть, но как раз то самое "Программуля".

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

[sirs]

Артур: тогда не берите в расчет мой ответ) а смотрите в сторону алгоритмов нечеткого поиска Как определить похожесть двух строк? . Но тут вам для начала нужно определиться с критериями, т.е. насколько похожим должно быть слово. Плюс, вы упомянули базу. Тогда почему просто не использовать средства для поиска самой БД? Какую БД вы планируете использовать?

[Артур]

sirs: Я, наверное, погорячился сказав "База". Это будет текстовый документ, который я могу пропарсить и прочесть из него строки.
Тот вопрос " Как определить похожесть двух строк?" как раз мой :)
Там люди дали хорошие ответы, указали на Lucene. Только боюсь это сейчас слишком мощно для меня.
Изучая ответы набрел на тему, где говорили про поиск в индексе словаря, но не объясняли как это делается.
Тут у меня и возникла идея, сделать "самопальный" алгоритм, параллельно разбираясь с Lucene.

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

[sirs]

Артур: Ох, сорри, сразу не заметил, что авторы одинаковые в вопросах. Хорошо, тогда чтобы максимально упросить задачу, предлагаю вам разбить ее еще на более мелкие части:
1) определиться с критериями "похожести" ключевых слов, например сколько символов может отличаться и т.д. и какой % вероятности ошибки для вас приемлем;
2) найти максимально простой алгоритм "нечеткого поиска", который можно реализовать самому (но вы должны понимать, что у него будет большой % ошибок);
3) написать реализация для заполнения словаря;
4) написать реализацию для поиска в словаре.

[Артур]

sirs: ну что Вы, не надо "сорри" :).
Написание этого поста с вопросом и есть части реализации более мелких задач.
3) написать реализация для заполнения словаря;
- тут , например, пользуемся описанной Вами ниже схемы, где в HashMap добавляются слова keyword-ы. Получаем некий индекс, где слова ссылаются на исходные целые фразы
4) написать реализацию для поиска в словаре.
- вот тут и вопрос. Я понимаю, как найти по одному ключевому слову в запросе. А если ключевых слов несколько в запросе, как выбрать из полученного списка результата именно то, что нужно? Некое пересечение результатов?

[sirs]

Артур: Артур: Не знаю, видели вы или нет этот вопрос stackoverflow.com/questions/21057708/java-fuzzy-st... там упоминается https://commons.apache.org/proper/commons-lang/jav..., java.lang.CharSequence) т.е. можно получиться "LevenshteinDistance" между двух строк по сути и сравнить удовлетворят ли вас эта дистанция, если удовлетворяет - результат найдет, если не удовлетворяет - ищем дальше.

Смотрите, по п.3 такая реализация подойдет только, если мы будем искать точное совпадение подстроки в строке, для похожих стрингов она не подходит.

[Артур]

sirs: Sirs, спасибо за ссылки, надо будет ознакомиться.
А все таки, как примерно ищется в словаре, если в ключевом запросе несколько строк? Есть какое-то объяснение абстрактно- пальцевое?)))

Answer 1

[sirs]

Тогда для быстрого старта я предлагаю вам использовать HashMap. В качестве ключей используете ключевые слова из названия программ, например:

Map<String, List<Software>> dictionary = new HashMap();
        List<Software> list = new ArrayList<Software>();
        programs.add(new Software("Программуля плюс"));
        programs.add(new Software("Программуля для детей"));
        programs.add(new Software("Автобусы. Программуля"));
        dictionary.put("Программуля", list);

и т.д.
Все ваши эталонные названия программ дробите на отдельные слова, объявляете каждое такое слово keywords. Тут нужно вводить ограничения на такие слова, например не менее 3 букв и только буквы и т.п. - тут вы должны сами определиться. Далее составляете списки программ, в которых встречаются такие ключевые слова, проверить если ли такая подстрока в строке - str1.toLowerCase().contains(str2.toLowerCase()).
Поиск в полученном словаре просто по ключу dictionary.get("Программуля "); - вернет вам список программ, в которых встречается искомая подстрока. Тут тоже перед тем как опрашивать - можно слегка оптимизировать, например привести к одному регистру, убрать пробелы в начале и конце и т.д.
Это самая простая реализация. Она не будет учитывать "похожие" слова, только совпадение подстроки в строке.
Сделайте все на интерфейсах, в процессе по линкам выше наберетесь знаний и сделаете более крутую реализацию, оставив интерфейс старым, подменив только реализацию.

Comments

[Артур]

Как-то так я это и представлял. Даже почти решил проблему "похожести" слов через тупое сравнение на совпадение символов ( коряво, но какие-то результаты даст. Программуля == програмуля).
А вот вопрос. Когда я получу по ключевому слову из строки список эталонных названий, я перейду к поиску по второму слову. Этот поиск даст мне еще список строк, в которых встречается "слово keywords".
А как быть дальше? Проверить на совпадение во всех случаях ( или на какой-то процент совпадений)?

[Артур]

я размышлял примерно так:
В справочнике у меня есть список слов, полученный из строк эталонов. Каждое из этих слов ссылается на оригинальную строку.
Допустим я разбил пользовательский запрос на слова и сравниваю со словами справочника. Тот факт, что я в строке пользователя нахожу слово из справочника уже дает мне намек на то, что запрос есть в базе. Слова "без особого смысла", такие как "программка для документов" не будут давать результата, остается совпадение по "Программуля". Считать пользовательскую строку похожей.
Может разным словам, которые точно имеют смысл, типа "Программуля" дать в справочнике рейтинг выше...

[sirs]

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

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

[Артур]

sirs: "Искать по совпадению символов - очень плохой вариант, если честно, проблемы со скоростью и памятью гарантированы. Тем более могут быть слова с идентичным массивом символов, но разным порядком следования. "
- полностью согласен. Если я не разберусь с более умными вариантами, не останется ничего другого :) Благо объемы не очень большие.

"Артур: Смотрите, в любой случае на входе мы ждем строку, а на выходе - список программ с похожими названиями, я верно считаю? или условие - вернуть одну максимально похожую программу?"
- по-хорошему, на выходе я жду либо фразу "Такой программы нет в справочнике", максимально похожую.

Answer 2

[xmoonlight]

Как определить похожесть двух строк?

Comments

[Артур]

xmoonlight Спасибо за комментарий. ;)

Answer 3

[Roman_Kh]

Вам нужен нечеткий поиск. Начальный экскурс в тему можно получить здесь и здесь.

Comments

[Артур]

Спасибо за комментарий.
Искал уже по этой теме. Сейчас понимаю, что этот алгоритм не осилю в силу сроков.