Java: Поиск в ключах HashMap на основе регулярных выражений?

Question

Я строю тезаурус, используя HashMap для хранения синонимов.

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

public ArrayList<String> searchDefinition(String regex) {
    ArrayList<String> results = new ArrayList<String>();

    Pattern p = Pattern.compile(regex);

    Set<String> keys = thesaurus.keySet();
    Iterator<String> ite = keys.iterator();

    while (ite.hasNext()) {
        String candidate = ite.next();
        Matcher m = p.matcher(candidate);
        System.out.println("Attempting to match: " + candidate + " to "  + regex);
        if (m.matches()) {
            System.out.println("it matches");
            results.add(candidate);
        }
    }   

    if (results.isEmpty()) {
        return null;
    }
    else {
        return results;
    }
}

Теперь это не работает так, как я ожидал (или, возможно, я неправильно использую регулярные выражения). Если у меня есть следующие ключи в hashmap:

cat, car, chopper

затем, позвонив searchDefinition("c") или searchDefinition("c*"), я получу null.

1. Как мне заставить эту работу работать как положено?
2. Существует ли лучшая структура данных, чем в HashMap, для сохранения graph подобного, необходимого тезаурусу? (только из любопытства, поскольку для этого задания нас просят использовать Java Collection Map).
3. Что-нибудь еще, что я делаю неуместно в приведенном выше коде?

Спасибо, Dan

РЕДАКТИРОВАТЬ: я исправил пример. Это не работает, даже если я использую правильный регистр.

Answer 1

Но, хм:

(a) Зачем вам использовать HashMap, если вы собираетесь всегда искать его последовательно? На обработку хеш-ключей и т. Д. Уходит много лишних затрат, когда вы их никогда не используете Конечно, лучше использовать простой ArrayList или LinkedList.

(б) Какое это имеет отношение к тезаурусу? Зачем вам искать в тезаурусе регулярные выражения? Если бы я хотел знать синонимы, скажем, «кот», я бы подумал, что я буду искать «кот», а не «с. *».

Моя первая мысль о том, как построить тезаурус, была бы ... ну, я думаю, первый вопрос, который я задам, это: "Является ли синоним отношением эквивалентности?", Т.е. если А является синонимом для В, не так ли? следовать, что B является синонимом A? И если A является синонимом для B, а B является синонимом для C, то является ли A синонимом для C? Если предположить, что ответы на эти вопросы «да», то мы хотим построить что-то, что делит все слова в языке на наборы синонимов, поэтому мы можем сопоставить любое слово в каждом наборе со всеми другими словами в этом наборе. , Так что вам нужен способ взять любое слово, сопоставить его с какой-либо точкой связи, а затем перейти от этой точки связи ко всем словам, которые соответствуют ему.

Это было бы просто для базы данных: просто создайте таблицу с двумя столбцами, скажем «word» и «token», каждый со своим собственным индексом. Все синонимы отображаются на один и тот же токен. Маркер может быть любым, если он уникален для любого заданного набора синонимов, например порядковый номер. Затем найдите данное слово, найдите соответствующий токен, а затем получите все слова с этим токеном. Например, мы можем создать записи с (большой, 1), (большой, 1), (гигантский, 1), (кошка, 2), (кошачий, 2) и т. Д. Поиск «большой» и вы получите 1, затем Ищите 1, и вы получите "большой", "большой" и "гигант".

Я не знаю ни одного класса во встроенных коллекциях Java, который бы делал это. Самый простой способ, который я могу придумать, - это создать две скоординированные хеш-таблицы: одну, которая отображает слова в токены, а другую, которая отображает токены в массив слов. Таким образом, таблица 1 может иметь большие-> 1, большие-> 1, гигантские-> 1, кошка-> 2, кошачьи-> 2 и т. Д. Тогда таблица 2 отображает 1 -> [большой-большой-гигантский], 2-> [кошка, кошка] и т. д. Вы смотрите в первой таблице, чтобы сопоставить слово токену, а во второй - чтобы сопоставить этот токен со списком слов. Это неуклюже, потому что все данные хранятся избыточно, может быть, есть лучшее решение, но я не собираюсь забирать его из головы. (Что ж, было бы легко, если бы мы предполагали, что будем каждый раз последовательно искать по всему списку слов, но производительность может ухудшиться, когда список станет большим.)

Answer 2

Необходимо указать нечувствительность к регистру Pattern.compile ( "c", Pattern.CASE_INSENSITIVE ). Чтобы найти слово с c, вам нужно использовать matcher.find () . Matcher.matches () пытается сопоставить всю строку.

Answer 3

Это регулярное выражение, которое вы используете?

Метод Matcher.matches () возвращает true, только если вся входная последовательность соответствует выражению (из Javadoc), поэтому вам нужно будет использовать "c.*" в этом случае, а не "c*", а также соответствующий регистр бесчувственно.

Answer 4

Похоже, вы используете свои регулярные выражения неуместно. «c» будет соответствовать только нижнему регистру c, а не верхнему.

При этом я бы посоветовал вам использовать встроенную базу данных с возможностями полнотекстового поиска.

Answer 5

Регулярные выражения чувствительны к регистру. Вы хотите:

Pattern p = Pattern.compile(regex, Pattern.CASE_INSENSITIVE);

Answer 6

Отвечая на Джея "Но Хм" выше,

(я бы добавил комментарий, но у меня нет представителя)

Последовательный поиск делает это медленно. Делать это с регулярными выражениями - значит погрузиться в безумие. Делать это с базой данных - программный полицейский. Конечно, если ваш набор данных был массивным, что может потребоваться, но помните: «для этого задания нас просят использовать Java Collection Map». Мы должны выяснить, как правильно использовать эту коллекцию Java.

Причина, по которой это не очевидно, заключается в том, что это не одна коллекция. Это два. Но это не две карты. Это не ArrayList. Чего не хватает, так это набора. Это карта наборов синонимов.

Set позволит вам создавать свои списки синонимов. Вы можете сделать столько, сколько захотите. Два набора синонимов послужат хорошим примером. Это набор, а не ArrayList, потому что вам не нужны повторяющиеся слова.

Карта > позволит вам быстро найти путь от любого слова к его синониму.

Создайте свои наборы. Затем постройте карту. Напишите вспомогательный метод для построения карты, которая берет карту и набор.

addSet (Карта > map, Set newSet)

Этот метод просто зацикливает newSet и добавляет строки на карту в качестве ключей и ссылку на newSet в качестве значения. Вы должны вызывать addSet один раз для каждого набора.

Теперь, когда ваша структура данных построена, мы должны быть в состоянии найти материал. Чтобы сделать это немного более надежным, не забудьте очистить свой ключ поиска, прежде чем искать. Используйте trim (), чтобы избавиться от бессмысленных пробелов. Используйте toLowerCase (), чтобы избавиться от бессмысленного использования заглавных букв. Вы должны были сделать оба этих действия на данных синонимов до (или во время) построения наборов. Делайте это, и кому нужны регулярные выражения для этого? Этот способ намного быстрее и, что еще важнее, безопаснее. Регулярные выражения очень мощные, но могут быть кошмаром для отладки, когда они идут не так, как надо. Не используйте их только потому, что вы думаете, что они крутые.