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, чтобы поддерживать , как это требуется тезаурусом? (только любопытство, так как для этого задания нам предлагается использовать карту Java Collection).
3. Что-нибудь еще, что я делаю innapropriately в коде выше?

Спасибо, Dan

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

Answer 1

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

Answer 2

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

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

Answer 3

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

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

Answer 4

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

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

Answer 5

Но, гм:

(а) Почему бы вам использовать HashMap, если вы собираетесь всегда искать его последовательно? Для обработки хеш-ключей и всего того, что вы никогда не используете, это слишком много лишних затрат. Разумеется, простая идея ArrayList или LinkedList была бы лучшей идеей.

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

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

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

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

Answer 6

Реагируя на Джея «Но Хмм» выше ,

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

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

Причина не очевидна, потому что это не одна коллекция. Это два. Но это не две карты. Это не ArrayList. Отсутствует набор. Это карта для синонимов.

<String> позволит вам создавать списки синонимов. Вы можете сделать столько, сколько хотите. Хорошим примером может служить два набора синонимов. Это Set не ArrayList, потому что вы не хотите дублировать слова.

< String, Set <String> > позволит вам быстро найти путь от любого слова до его набора синонимов.

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

addSet (Карта < String, Set < Строка > > карта, набор < Строка > Newset)

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

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