Java: recherche dans les clés HashMap basées sur regex?

Je suis en train de construire un dictionnaire des synonymes à l'aide d'une table de hachage pour stocker les synonymes.

Je suis en train de rechercher les mots en se basant sur une expression régulière: la méthode devra prendre une chaîne de caractères comme paramètre et retourne un tableau de résultats. Voici mon premier coup de couteau à elle:

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;
    }
}

Maintenant, cela ne fonctionne pas comme je m'attends (ou peut-être que je suis en utilisant des expressions régulières à tort). Si j'ai les clés suivantes dans la table de hachage:

cat, car, chopper

puis en appelant searchDefinition("c") ou searchDefinition("c*") - je obtenir null.

Comment puis-je faire ce travail comme prévu?
Est-il une meilleure structure de données que la table de hachage pour garder un graph comme nécessaire par un thésaurus? (curiosité seulement, comme pour cette mission, vous êtes invités à utiliser de Java Collection de Carte).
Autre chose que je suis en train de faire innapropriately dans le code ci-dessus?

Grâce,
Dan

EDIT: j'ai corrigé l'exemple. Il ne fonctionne pas, même si j'utilise la bonne affaire.

source d'informationauteur Dan

10

Vous devez spécifier le compte de la casse De modèle.compiler( "c",De modèle.CASE_INSENSITIVE ). Pour trouver un mot avec un c en lui, vous devez utiliser matcher.find(). Matcher.correspond à() essaie de faire correspondre l'ensemble de la chaîne.
10

Mais, hmm:

(a) Pourquoi voudriez-vous utiliser une HashMap si vous avez l'intention de toujours rechercher de façon séquentielle? C'est beaucoup de gaspillage de frais généraux pour traiter les clés de hachage et de tous les lorsque vous n'utilisez jamais. Sûrement une simple liste de tableaux ou LinkedList serait une meilleure idée.

(b) Qu'est-ce que avez à faire avec un dictionnaire des synonymes? Pourquoi voulez-vous rechercher un dictionnaire des synonymes en utilisant des expressions régulières? Si je veux savoir des synonymes pour, disons, "chat", je pense que j'aurais de la recherche pour "chat", pas de "c.*".

Ma première pensée sur la façon de construire un dictionnaire des synonymes, ce serait ... bien, je crois que la première question que je voudrais poser est: "Est synonyme d'une equivalance relation?", c'est à dire si l'Un est synonyme de B, est-ce que B est un synonyme pour une? Et si A est un synonyme de B et B est synonyme de C, alors il est Un synonyme de C? En supposant que la réponse à ces questions est "oui", alors ce que nous voulons construire est quelque chose qui divise tous les mots de la langue en ensembles de synonymes, de sorte que nous pouvons ensuite la carte sur un mot dans chaque ensemble de tous les autres mots dans ce jeu. Donc, ce que vous avez besoin est une façon de prendre n'importe quel mot, carte il à une sorte de point de connexion, et puis aller à partir de ce point de connexion pour tous les mots qu'carte.

Ce serait simple sur une base de données: il suffit de créer un tableau avec deux colonnes, dire "mot" et de "jeton", chacun avec son propre index. Tous les synonymes de la carte à la même jeton. Le jeton peut être n'importe quoi tant que son unique pour un ensemble donné de synonymes, comme un numéro de séquence. Ensuite, la recherche de la parole donnée, de trouver le jeton associé, et puis obtenir tous les mots avec le jeton. Par exemple, nous pourrions créer des dossiers avec des (gros,1), (grande,1), (gigantesque,1), (chat,2), (chats,2), etc. Recherche pour "big" et vous obtenez 1, puis de rechercher les 1 et vous obtenez "grand", "grand", et "géant".

Je ne sais pas de toute sa classe dans le haut-Java collections qui fait cela. La meilleure façon que je peux penser à est de construire deux coordonnée des tables de hachage: l'Une des cartes de mots pour les jetons, et un autre que les cartes de jetons à un tableau de mots. Si le tableau 1 peut avoir de gros->1, la grande->1, gigantesque->1, cat->2, féline->2, etc. Puis le tableau 2 cartes 1->[gros,grand,gigantesque], 2->[chat,félin], etc. Vous regardez dans la première table pour un mot pour un jeton, et dans la seconde à la carte jeton de retour à une liste de mots. Il est maladroit, car toutes les données sont stockées de manière redondante, peut-être il y a une meilleure solution, mais je ne suis pas le faire sur le haut de ma tête. (Eh bien, il serait facile si nous supposons que nous allons séquentiellement de recherche de l'ensemble de la liste de mots à chaque fois, mais la performance ne sucer que la liste a de grands.)
3

Est que l'expression régulière que vous utilisez?

Le Matcher.correspond à() la méthode renvoie true uniquement si la totalité de l'ensemble de la séquence d'entrée correspond à l'expression (à partir de la Javadoc), de sorte que vous devez utiliser "c.*" dans ce cas, pas "c*" ainsi que l'appariement des cas insensiblement.
2

Les expressions régulières sont sensibles à la casse. Vous souhaitez:
```
Pattern p = Pattern.compile(regex, Pattern.CASE_INSENSITIVE);
```
2

On dirait que vous êtes en utilisant votre regexes de façon inappropriée". c", seulement correspondre à une baisse du cas c, pas de majuscules.

Cela dit, j'aimerais vous suggère de regarder dans l'aide d'une base de données intégrée avec plein de fonctions de recherche de texte.
0

De répondre à Jay de "Mais Hmm" ci-dessus,

(J'aimerais ajouter un commentaire, mais n'ont pas la rep.)

De la recherche de façon séquentielle est de le faire de la même façon lente. De le faire avec des expressions régulières est de descendre dans la folie. De le faire avec une base de données est une programmation cop. Assurez-vous si votre jeu de données a été massive qui pourrait être nécessaire, mais rappelez-vous "pour cette mission, nous sommes invités à utiliser de Java Collection Carte" Nous devrions être de trouver la bonne façon d'utiliser ce java collection.

La raison pour laquelle il n'est pas évident, c'est parce qu'il n'en est pas une collection. C'est deux. Mais il n'est pas deux cartes. Ce n'est pas une liste de tableaux. Ce qui manque, c'est un Ensemble. C'est une carte à des ensembles de synonymes.

Set<String> vous permettra de créer vos listes de synonymes. Vous pouvez faire autant que vous le souhaitez. Deux ensembles de synonymes ferait un bon exemple. C'est un Jeu pas une liste de tableaux parce que vous ne voulez pas de double mots.

Map<String, Set<String>> vous permettra de trouver rapidement votre chemin à partir de n'importe quel mot à son synonyme ensemble.

Construire vos jeux. Puis construire la carte. Écrire une méthode d'aide à construire la carte qui prend une carte et d'un ensemble.

addSet(Map<String, Set<String>> map, Set<String> newSet)

Cette méthode boucles newSet et ajoute les chaînes à la carte comme les clés, et la référence à newSet en tant que valeur. Vous souhaitez appeler addSet une fois pour toutes.

Maintenant que vous êtes à la structure de données est construit, nous devrions être en mesure de trouver des trucs. Pour rendre cela un peu plus robuste, n'oubliez pas de nettoyer votre clé de recherche avant de vous recherchez. Utiliser trim() pour se débarrasser de signification des espaces. Utilisation toLowerCase() pour se débarrasser de sens de la capitalisation. Vous devriez avoir fait ces deux sur le synonyme données avant (ou pendant) la construction des ensembles. Le faire et qui a besoin d'expressions régulières pour cela? De cette manière est beaucoup plus rapide et surtout plus sûr. Les Expressions régulières sont très puissants, mais peut être un cauchemar à déboguer quand elles vont mal. Ne les utilisez pas juste parce que vous pensez qu'ils sont cool.

Vous devez vous connecter pour publier un commentaire.