45

どの構造が最高のパフォーマンス結果を提供しますか。トライ（プレフィックスツリー）、サフィックスツリーまたはサフィックス配列？他に同様の構造はありますか？これらの構造の優れたJava実装は何ですか？

編集：この場合、テキスト上の辞書の名前を識別するために、名前の大きな辞書と自然言語のテキストの大きなセットの間で文字列照合を行いたいと思います。

4

7 に答える 7

65

トライは、この種のデータ構造が最初に発見されたものです。

接尾辞ツリーは、トライを改良したものです（線形エラー検索を可能にする接尾辞リンクがあり、接尾辞ツリーはトライの不要なブランチをトリミングするため、それほど多くのスペースを必要としません）。

接尾辞配列は、接尾辞ツリーに基づいたデータ構造を取り除いたものです（接尾辞リンクはありません（エラーの一致が遅い）が、パターンの一致は非常に高速です）。

トライはスペースを消費しすぎるため、実際には使用できません。

接尾辞木は、トライよりも軽量で高速であり、DNAのインデックス作成や、一部の大規模なWeb検索エンジンの最適化に使用されます。

一部のパターン検索では、接尾辞配列は接尾辞ツリーよりも低速ですが、使用するスペースが少なく、接尾辞ツリーよりも広く使用されています。

同じデータ構造ファミリー：

他にも実装があります。CSTは、接尾辞配列といくつかの追加のデータ構造を使用して接尾辞ツリーの検索機能を取得する接尾辞ツリーの実装です。

FCSTはさらに進んで、接尾辞配列を使用してサンプルの接尾辞ツリーを実装します。

DFCSTは、FCSTの動的バージョンです。

拡大する：

2つの重要な要素は、スペースの使用と操作の実行時間です。現代のマシンでは、これは関係ないと思うかもしれませんが、1人の人間のDNAにインデックスを付けるには、40ギガバイトのメモリが必要になります（非圧縮および最適化されていないサフィックスツリーを使用）。そして、これだけのデータでこのインデックスの1つを構築するには、数日かかる場合があります。Googleを想像してみてください。検索可能なデータがたくさんあり、すべてのWebデータに対して大きなインデックスが必要であり、誰かがWebページを作成するたびにインデックスを変更することはありません。そのための何らかの形式のキャッシュがあります。ただし、メインインデックスはおそらく静的です。そして、数週間ごとに、すべての新しいWebサイトとデータを収集し、新しいインデックスを作成して、新しいものが完成したときに古いものを置き換えます。インデックス作成にどのアルゴリズムを使用しているかはわかりませんが、パーティション化されたデータベース上のサフィックスツリープロパティを持つサフィックス配列である可能性があります。

CSTは8ギガバイトを使用しますが、接尾辞木の操作速度は大幅に低下します。

接尾辞配列は、約700メガから2ギガで同じことを行うことができます。ただし、接尾辞配列が付いたDNAには遺伝的エラーはありません（つまり、ワイルドカードを使用したパターンの検索ははるかに遅くなります）。

FCST（完全に圧縮された接尾辞木）は、800〜1.5ギガで接尾辞木を作成できます。CSTに向かって速度がかなり低下します。

DFCSTはFCSTよりも20％多いスペースを使用し、FCSTの静的実装の速度を低下させます（ただし、動的インデックスは非常に重要です）。

動作速度を向上させてデータ構造のRAMスペースのコストを補うことは非常に難しいため、接尾辞ツリーの実行可能な（スペースに関して）実装は多くありません。

とはいえ、接尾辞木には、エラーとのパターンマッチングに関する非常に興味深い検索結果があります。エイホコラシックはそれほど速くはなく（一部の操作ではほぼ同じくらい速く、エラーマッチングではありません）、ボイヤームーア文字はほこりの中に残ります。

于 2011-07-17T10:43:09.193 に答える
4

どのような操作を計画していますか？ libdivsufsortは、かつてCで最高の接尾辞配列の実装でした。

于 2011-03-31T01:01:57.083 に答える
2

接尾辞木を使用すると、O（n + m + k）時間で辞書をテキストに一致させるものを書くことができます。ここで、nは辞書の文字、mはテキストの文字、kは一致数です。このための試行ははるかに遅くなります。接尾辞配列が何であるかわからないので、それについてコメントすることはできません。

とは言うものの、コーディングするのは簡単ではなく、必要な機能を提供するJavaライブラリーを私は偶然知りません。

于 2010-03-21T16:12:22.227 に答える
1

編集：この場合、テキスト上の辞書の名前を識別するために、名前の大きな辞書と自然言語のテキストの大きなセットの間で文字列照合を行いたいと思います。

これは、 Aho-Corasickアルゴリズムのアプリケーションのように聞こえます。辞書からオートマトンを（線形時間で）構築します。これを使用して、複数のテキスト内の辞書の単語のすべての出現を（線形時間で）見つけることができます。

（ウィキペディアページの「外部リンク」セクションからリンクされているこれらの講義ノートの説明は、ページ自体の説明よりもはるかに読みやすいです。）

于 2010-03-21T17:51:21.260 に答える
1

私はサフィックスオートマシンが好きです。あなたは私のウェブサイトを通してより多くの詳細を見つけることができます： http ：//www.fogsail.net/2019/03/06/20190306/

ここに画像の説明を入力してください

まず、通常の構造を使用した場合、すべての接尾辞を移動するにはO（n ^ 2）が必要です

基数ソートを使用して、接尾辞配列を最初の文字でソートします。

ただし、最初の文字を並べ替えると、その情報を使用できます。

詳細は画像で示されています（中国語は無視してください）

配列を最初のキーで並べ替えると、結果は赤い長方形で表示されます

,,....--->,,...。

ここに画像の説明を入力してください

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn = 1001 * 100 + 10;

struct suffixArray {
    int str[maxn], sa[maxn], rank[maxn], lcp[maxn];
    int c[maxn], t1[maxn], t2[maxn];
    int n;

    void init() { n = 0; memset(sa, 0, sizeof(sa)); }

    void buildSa(int Rdx) {
        int i, *x = t1, *y = t2;
        for(i = 0; i < Rdx; i++) c[i] = 0;
        for(i = 0; i < n; i++) c[x[i] = str[i]]++;
        for(i = 1; i < Rdx; i++) c[i] += c[i-1];
        for(i = n-1; i >= 0; i--) sa[--c[x[i]]] = i;

        for(int offset = 1; offset <= n; offset <<= 1) {
            int p = 0;
            for(i = n-offset; i < n; i++) y[p++] = i;
            for(i = 0; i < n; i++) if(sa[i] >= offset) y[p++] = sa[i] - offset;

            // radix sort
            for(i = 0; i < Rdx; i++) c[i] = 0;
            for(i = 0; i < n; i++) c[x[y[i]]]++;
            for(i = 1; i < Rdx; i++) c[i] += c[i-1];
            for(i = n-1; i >= 0; i--) { sa[--c[x[y[i]]]] = y[i]; y[i] = 0; }

            // rebuild x and y
            swap(x, y); x[sa[0]] = 0; p = 1;
            for(i = 1; i < n; i++)
                x[sa[i]] = y[sa[i-1]] == y[sa[i]] && y[sa[i-1]+offset] == y[sa[i]+offset] ? p-1 : p++;
            if(p >= n) break;
            Rdx = p;
        }
    }
于 2019-05-19T09:20:08.687 に答える
0

誘導ソートアルゴリズム（saisと呼ばれる）のこの実装には、接尾辞配列を構築するためのJavaバージョンがあります。

于 2011-07-15T20:56:45.473 に答える
0

トライvsサフィックスツリー

両方のデータ構造により、非常に高速なルックアップが保証されます。検索時間はクエリワードの長さに比例し、複雑度時間O（m）です。ここでmはクエリワードの長さです。

これは、10文字のクエリワードがある場合、それを見つけるために最大10ステップが必要であることを意味します。

Trie：一般的なプレフィックスごとに1つのノードがある文字列を格納するためのツリー。文字列は追加のリーフノードに保存されます。

接尾辞木：1つの子を持つすべてのノードが親とマージされる、特定の文字列の接尾辞に対応するトライのコンパクトな表現。

defはからです：アルゴリズムとデータ構造の辞書

一般に、辞書の単語（辞書）または文字列の任意のセットのインデックスを作成するために使用されるTrieの例D = {abcd、abcdd、bxcdf、.....、zzzz}

テキストのすべてのサフィックスに同じデータ構造「Trie」を使用してテキストにインデックスを付けるために使用されるサフィックスツリーT=abcdabcg T = {abcdabcg、abcdabc、abcdab、abcda、abcd、abc、ab、a}のすべてのサフィックス

今では文字列のグループのように見えます。この文字列のグループ（Tのすべての接尾辞）の上にTrieを構築します。

両方のデータ構造の構築は線形であり、時間と空間でO（n）を必要とします。

dicionary（文字列のセット）の場合：n=すべての単語の文字の合計。テキスト内：n=テキストの長さ。

接尾辞配列：圧縮された接尾辞で接尾辞ツリーを表す技術であり、文字列の接尾辞のすべての開始位置の配列です。

検索時間は接尾辞木よりも遅いです。

詳細については、ウィキペディアにアクセスしてください。このトピックについて話している良い記事があります。

于 2014-03-17T13:55:37.017 に答える