1

都市がキーで州が値である <city, state> ペアを格納する HashMap があります。現在、都市名は「ニューデリー」のように複数の単語で構成されている場合があります。現在、都市名が含まれている場合と含まれていない場合がある多くの文があります。それぞれについて確認したい。

1 つのアプローチは、HashMap をスキャンし、各キーが文に存在するかどうかを確認することです。しかし、HashMap が何百万ものエントリである場合、非常に非効率的なアプローチになります。

そのため、同じことを行うための効率的なアプローチがあるかどうかを探しています。ありがとうございました。

4

2 に答える 2

1

1、文を単語に分割し、都市名を単語に分割すると、ハッシュで確認できます。

2、アルゴリズムのアイデア:

AC FSM では、多くの文字列と文を 1 回で一致させることができます。

Suffix Tree、もう 1 つのアルゴリズム。

どちらも似ていると思います。どちらかを選んでください。

于 2013-01-08T03:01:04.770 に答える
0

試す

    TreeMap<String, String> map = new TreeMap<>();
    map.put("Delhi", "State");
    map.put("New Delhi", "State");
    map.put("New York", "State");
    String[] a = map.keySet().toArray(new String[0]);
    Set<String> found = new HashSet<>();

    Scanner s = new Scanner("First is Delhi, next is New Delhi");
    s.useDelimiter("[ .,\n\t\r]");
    String prev = "";    // previous word
    while (s.hasNext()) {
        String n = s.next();
        if (!prev.isEmpty()) {
            n = prev + n;
        }
        int i = Arrays.binarySearch(a, n);
        if (i >= 0) {
            found.add(n);
            prev = "";
        } else {
            i = -i - 1;
            if (i < a.length && a[i].startsWith(n)) {
                prev = n + " ";
            } else {
                prev = "";
            }
        }
    }
    System.out.println(found);

出力

[New Delhi, Delhi]

いくつかのバグがあるかもしれませんが、ソートされた String 配列 (都市) と Arrays.binarySearch を使用して、挿入位置をすばやく見つけ、要素 (都市) が現在の単語で始まるかどうかを確認するという考えです。

于 2013-01-08T04:46:57.240 に答える