23

何千もの高速な文字列検索とプレフィックス チェックを必要とするモバイル アプリを作成しています。これをスピードアップするために、約 180,000 語の単語リストからトライを作成しました。

すべてが素晴らしいのですが、唯一の問題は、この巨大なトライ (ノード数は約 400,000) を構築するのに、現在私の電話で約10 秒かかり、非常に遅いことです。

トライを構築するコードは次のとおりです。

public SimpleTrie makeTrie(String file) throws Exception {
    String line;
    SimpleTrie trie = new SimpleTrie();

    BufferedReader br = new BufferedReader(new FileReader(file));
    while( (line = br.readLine()) != null) {
        trie.insert(line);
    }
    br.close();

    return trie;
}

insertで実行されるメソッドO(length of key)

public void insert(String key) {
    TrieNode crawler = root;
    for(int level=0 ; level < key.length() ; level++) {
        int index = key.charAt(level) - 'A';
        if(crawler.children[index] == null) {
            crawler.children[index] = getNode();
        }
        crawler = crawler.children[index];
    }
    crawler.valid = true;
}

トライをより速く構築するための直感的な方法を探しています。ラップトップで一度だけトライをビルドし、何らかの方法でディスクに保存し、電話のファイルからロードしますか? しかし、これを実装する方法がわかりません。

または、構築に時間がかからず、同様の検索時間の複雑さを持つ他のプレフィックスデータ構造はありますか?

任意の提案をいただければ幸いです。前もって感謝します。

編集

誰かが Java シリアライゼーションの使用を提案しました。私はそれを試しましたが、このコードでは非常に遅かったです:

public void serializeTrie(SimpleTrie trie, String file) {
        try {
            ObjectOutput out = new ObjectOutputStream(new BufferedOutputStream(new FileOutputStream(file)));
            out.writeObject(trie);
            out.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public SimpleTrie deserializeTrie(String file) {
        try {
            ObjectInput in = new ObjectInputStream(new BufferedInputStream(new FileInputStream(file)));
            SimpleTrie trie = (SimpleTrie)in.readObject();
            in.close();
            return trie;
        } catch (IOException | ClassNotFoundException e) {
            e.printStackTrace();
            return null;
        }
    }

この上記のコードを高速化できますか?

私の試み: http://pastebin.com/QkFisi09

単語リスト: http://www.isc.ro/lists/twl06.zip

コードの実行に使用される Android IDE: http://play.google.com/store/apps/details?id=com.jimmychen.app.sand

4

10 に答える 10

25

Double-Array 試行は、すべてのデータが線形配列に保存されるため、保存/読み込みが非常に高速です。検索も非常に高速ですが、挿入にはコストがかかる場合があります。どこかにJavaの実装があるに違いない。

また、データが静的な場合 (つまり、電話で更新しない場合)は、タスクにDAFSAを検討してください。これは、単語を格納するための最も効率的なデータ構造の 1 つです (サイズと速度の両方の点で「標準的な」試行と基数試行よりも優れている必要があり、速度の点で簡潔な試行よりも優れており、サイズの点で簡潔な試行よりも優れていることがよくあります)。優れた C++ 実装があります: dawgdic - これを使用してコマンド ラインから DAFSA を構築し、結果のデータ構造に Java リーダーを使用できます (実装例はこちら)。

于 2013-09-27T21:08:16.090 に答える
3

子ノードへの参照を配列インデックスに置き換えて、トライをノードの配列として保存できます。ルート ノードが最初の要素になります。そうすれば、単純なバイナリまたはテキスト形式からトライを簡単に保存/ロードできます。

public class SimpleTrie {
    public class TrieNode {
        boolean valid;
        int[] children;
    }
    private TrieNode[] nodes;
    private int numberOfNodes;

    private TrieNode getNode() {
        TrieNode t = nodes[++numberOnNodes];
        return t;
    }
}
于 2013-09-27T18:50:46.150 に答える
3

大きな String[] を作成してソートするだけです。次に、バイナリ検索を使用して文字列の場所を見つけることができます。プレフィックスに基づいてクエリを実行することもできます。

プレフィックス検索の例:

比較方法:

private static int compare(String string, String prefix) {
    if (prefix.length()>string.length()) return Integer.MIN_VALUE;

    for (int i=0; i<prefix.length(); i++) {
        char s = string.charAt(i);
        char p = prefix.charAt(i);
        if (s!=p) {
            if (p<s) {
                // prefix is before string
                return -1;
            }
            // prefix is after string
            return 1;
        }
    }
    return 0;
}

配列内のプレフィックスの出現を検索し、その場所を返します (MIN または MAX は見つからないことを意味します)

private static int recursiveFind(String[] strings, String prefix, int start, int end) {
    if (start == end) {
        String lastValue = strings[start]; // start==end
        if (compare(lastValue,prefix)==0)
            return start; // start==end
        return Integer.MAX_VALUE;
    }

    int low = start;
    int high = end + 1; // zero indexed, so add one.
    int middle = low + ((high - low) / 2);

    String middleValue = strings[middle];
    int comp = compare(middleValue,prefix);
    if (comp == Integer.MIN_VALUE) return comp;
    if (comp==0)
        return middle;
    if (comp>0)
        return recursiveFind(strings, prefix, middle + 1, end);
    return recursiveFind(strings, prefix, start, middle - 1);
}

文字列配列と接頭辞を取得し、配列内の接頭辞の出現を出力します

private static boolean testPrefix(String[] strings, String prefix) {
    int i = recursiveFind(strings, prefix, 0, strings.length-1);
    if (i==Integer.MAX_VALUE || i==Integer.MIN_VALUE) {
        // not found
        return false;
    }
    // Found an occurrence, now search up and down for other occurrences
    int up = i+1;
    int down = i;
    while (down>=0) {
        String string = strings[down];
        if (compare(string,prefix)==0) {
            System.out.println(string);
        } else {
            break;
        }
        down--;
    }
    while (up<strings.length) {
        String string = strings[up];
        if (compare(string,prefix)==0) {
            System.out.println(string);
        } else {
            break;
        }
        up++;
    }
    return true;
}
于 2013-09-27T18:53:52.020 に答える
1

これは、トライをディスクに保存するためのかなりコンパクトな形式です。(効率的な) 逆シリアル化アルゴリズムによって指定します。初期内容がトライのルート ノードであるスタックを初期化します。文字を 1 つずつ読み、次のように解釈します。文字 AZ の意味は、「新しいノードを割り当て、それをスタックの現在の最上位の子にし、新しく割り当てられたノードをスタックにプッシュする」ことです。文字は、子がどの位置にいるかを示します。スペースの意味は、「スタックの一番上のノードの有効なフラグを true に設定する」ことです。バックスペース (\b) の意味は、「スタックをポップする」ことです。

たとえば、入力

TREE \b\bIE \b\b\bOO \b\b\b

単語リストを与える

TREE
TRIE
TOO

. デスクトップで、いずれかの方法を使用してトライを構築し、次の再帰アルゴリズム (疑似コード) によってシリアル化します。

serialize(node):
    if node is valid: put(' ')
    for letter in A-Z:
        if node has a child under letter:
            put(letter)
            serialize(child)
            put('\b')
于 2013-09-27T20:29:55.160 に答える
1

可能性のあるすべての子 (256) にスペースを事前に割り当てようとすると、膨大な量の無駄なスペースが生じます。あなたはあなたのキャッシュを泣かせています。子へのこれらのポインターをサイズ変更可能なデータ構造に格納します。

いくつかの試行では、1 つのノードで長い文字列を表すようにして最適化し、必要な場合にのみその文字列を分割します。

于 2013-09-28T04:45:36.893 に答える
0

空間効率が悪いのか、それとも時間効率が悪いのか? 普通のトライを転がしている場合は、モバイル デバイスを扱うときにスペースが問題の一部になる可能性があります。特にプレフィックス検索ツールとして使用している場合は、パトリシア/基数の試行を確認してください。

トライ: http://en.wikipedia.org/wiki/Trie

パトリシア/基数トライ: http://en.wikipedia.org/wiki/Radix_tree

言語については触れていませんが、Java でのプレフィックス試行の 2 つの実装を次に示します。

通常のトライ: http://github.com/phishman3579/java-algorithms-implementation/blob/master/src/com/jwetherell/algorithms/data_structures/Trie.java

パトリシア/基数 (スペース効率) トライ: http://github.com/phishman3579/java-algorithms-implementation/blob/master/src/com/jwetherell/algorithms/data_structures/PatriciaTrie.java

于 2013-09-23T23:02:49.713 に答える
0

配列のインデックスでノードをアドレス指定するという考えは好きではありませんが、それにはもう 1 つ追加 (ポインターへのインデックス) が必要だからです。ただし、事前に割り当てられたノードの配列を使用すると、割り当てと初期化にかかる時間を節約できます。また、リーフ ノード用に最初の 26 のインデックスを予約することで、多くのスペースを節約することもできます。したがって、180000 個のリーフ ノードを割り当てて初期化する必要はありません。

また、インデックスを使用すると、準備されたノード配列をディスクからバイナリ形式で読み取ることができます。これは数倍速くなければなりません。しかし、あなたの言語でこれを行う方法がわかりません。これはJavaですか？

ソース語彙がソートされていることを確認した場合は、現在の文字列のプレフィックスを前のものと比較することで時間を節約できます。たとえば、最初の 4 文字。それらが等しい場合、あなたはあなたを始めることができます

for(int level=0 ; level < key.length() ; level++) {

5 番目のレベルからループします。

于 2013-09-29T11:40:04.783 に答える