5

単語セットがあり、char バッグ (マルチセット) に基づいてそれらをクラスタリングしたいとします。例えば

{お茶、食べる、アッバ、アーブ、こんにちは}

にクラスター化されます

{{お茶、食べて}、{abba、aabb}、{こんにちは}}。

abbaとは、同じ char バッグ、つまり twoと twoaabbを持っているため、一緒にクラスター化されます。ab

効率的にするために、私が考えることができる素朴な方法は、たとえば、各単語を char-cnt シリーズに変換することでabbaありaabb、両方とも に変換されa2b2、 tea/eat は に変換されa1e1t1ます。辞書を作成し、同じキーで単語をグループ化できるようにします。

ここで 2 つの問題があります。まず、キーを作成するために文字を並べ替える必要があります。2 つ目は、文字列キーがぎこちなく見え、パフォーマンスが char/int キーほど良くないことです。

問題を解決するためのより効率的な方法はありますか?

4

7 に答える 7

1

x 文字のアルファベットと最大語長 y を使用すると、すべてのアナグラムが一意のハッシュを持つように (x + y) ビットのハッシュを作成できます。ビットの値 1 は、現在の文字に別の文字があることを意味し、値 0 は次の文字に移動することを意味します。これがどのように機能するかを示す例を次に示します。

7 文字のアルファベット (abcdefg) があり、最大単語長が 4 であるとします。すべての単語ハッシュは 11 ビットになります。「fade」という単語をハッシュしてみましょう: 10001010100

最初のビットは 1 で、プレゼントがあることを示します。2 番目のビットは、これ以上 a がないことを示します。3 番目のビットは、これ以上 b がないことを示します。これについて考える別の方法は、行内の 1 の数がその文字の数を表し、その 1 の文字列の前にあるゼロの合計がそれがどの文字であるかを表すということです。

「dada」のハッシュは次のとおりです: 11000110000

可能なハッシュと可能なアナグラムの間には 1 対 1 の対応があるため、これは任意の入力に対して一意のハッシュを与えることが保証されている最小の可能なハッシュであり、完了時にバケット内のすべてをチェックする必要がなくなることに注意してください。ハッシング。

大きなアルファベットと長い単語を使用すると、ハッシュ サイズが大きくなることは十分承知しています。このソリューションは、文字列の比較を避けるために一意のハッシュを保証することを目的としています。このハッシュを一定時間で計算するアルゴリズムを設計できる場合 (x と y の値がわかっている場合)、グループ化の問題全体を O(n) で解決できます。

于 2013-08-11T16:55:56.353 に答える
1

単語を並べ替えるので、すべての文字の ascii 値が 0 ～ 255 の範囲にあると想定します。次に、単語に対してCounting Sortを実行できます。

カウントソートには、入力ワードのサイズと同じ時間がかかります。ソートをカウントして得られた文字列の再構築には、O(wordlen) がかかります。このステップを O(wordLen) 未満にすることはできません。文字列を少なくとも 1 回繰り返す必要があるためです。つまり、O(wordLen) です。事前定義された順序はありません。その単語のすべての文字を反復せずに、その単語について何らかの仮定を立てることはできません。従来の並べ替えの実装 (つまり、比較ベースのもの) では、O(n * lg n) が得られます。しかし、非比較のものは O(n) を与えます。

リストのすべての単語を繰り返し処理し、カウント ソートを使用して並べ替えます。並べ替えられた単語のマップを、それらがマップする既知の単語のリストに保持します。リストへの要素の追加には一定の時間がかかります。したがって、全体的なアルゴリズムの複雑さは O(n * avgWordLength) です。

これがサンプル実装です

import java.util.ArrayList;


public class ClusterGen {

    static String sortWord(String w) {
        int freq[] = new int[256];

        for (char c : w.toCharArray()) {
            freq[c]++;
        }
        StringBuilder sortedWord = new StringBuilder();
        //It is at most O(n)
        for (int i = 0; i < freq.length; ++i) {
            for (int j = 0; j < freq[i]; ++j) {
                sortedWord.append((char)i);
            }
        }
        return sortedWord.toString();
    }

    static Map<String, List<String>> cluster(List<String> words) {
        Map<String, List<String>> allClusters = new HashMap<String, List<String>>();

        for (String word : words) {
            String sortedWord = sortWord(word);
            List<String> cluster = allClusters.get(sortedWord);
            if (cluster == null) {
                cluster = new ArrayList<String>();
            }
            cluster.add(word);
            allClusters.put(sortedWord, cluster);
        }

        return allClusters;
    }

    public static void main(String[] args) {
        System.out.println(cluster(Arrays.asList("tea", "eat", "abba", "aabb", "hello")));
        System.out.println(cluster(Arrays.asList("moon", "bat", "meal", "tab", "male")));

    }
}

戻り値

{aabb=[abba, aabb], ehllo=[hello], aet=[tea, eat]}
{abt=[bat, tab], aelm=[meal, male], mnoo=[moon]}
于 2013-08-11T07:29:57.280 に答える
0

私が行ったことの 1 つは、これと似ていますが、衝突を許容するために、文字を並べ替えてから重複を取り除くことです。したがって、あなたの例では、「aet」、「ab」、および「ehlo」のバケットがあります。

さて、私が言うように、これは衝突を可能にします。そのため、「ロッド」と「ドア」はどちらも同じバケツに入りますが、これは望ましくない場合があります。ただし、衝突は、簡単かつ迅速に検索できる小さなセットになります。

したがって、バケットの文字列を取得すると、それを 32 ビット整数 (少なくとも ASCII の場合) に変換できることがわかります。文字列内の各文字は、32 ビット整数のビットになります。したがって、「a」は最初のビット、「b」は 2 番目のビットなどです。すべての (英語の) 単語は、26 ビットの識別子を持つバケットを作成します。次に、非常に高速な整数比較を実行して、新しい単語が入るバケットを見つけたり、既存の単語が入っているバケットを見つけたりできます。

于 2013-08-11T01:55:54.630 に答える
0

Count the frequency of characters in each of the strings then build a hash table based on the frequency table. so for an example, for string aczda and aacdz we get 20110000000000000000000001. Using hash table we can partition all these strings in buckets in O(N).

于 2013-08-11T06:13:19.897 に答える