2

DAWGデータ構造にロードした500k以上のワードリストがあります。私のアプリは携帯電話用です。もちろん、この単語リストを DAWG にロードするために毎回すべての変換手順を繰り返したくはありません。これは、電話に単語リストを保持するには多くのストレージ スペースが必要であり、毎回 DAWG にロードするには多くの時間がかかるためです。 . そのため、DAWG のデータをファイルまたは DB に保存し、スペースを節約し、DAWG データ構造にすばやくロードできる形式で保存する方法を探しています。

各ノードを SQLite DB に保存できるという提案を 1 つ受け取りましたが、それが正確にどのように機能するのか、またそうするとどのようにすばやく取得できるのかわかりません。確かに、多くのクエリを実行したくありません。他のタイプの保存方法が良いでしょうか？また、シリアル化されたファイルを作成するか、ビットマップとして保存するという提案も受けました。

4

3 に答える 3

2

基本的にメモリ ダンプを実行できます。ポインタの代わりにオフセットを使用するだけです (Java 用語では、すべてのノードを配列に入れ、配列インデックスを使用してノードを参照します)。

500k は、特に DAWG がすでに非常に効率的であることを考えると、最近の携帯電話にとって問題となる量とは思えません。ファイルを mmap すると、データ構造がメモリに収まらなくても操作できます。

于 2010-12-13T13:58:49.393 に答える
1

ワードリストを減らしようとしましたか？アプリケーションで可能であれば、stamという単語だけを保存していますか？

一方、ワードリストは一定であるため、データ構造を再構築しないでください。提案されているようなメモリダンプを使用してみてください。ファイル、Javaシリアル化、またはピクルスピクルテクニックにmmapを使用して、既製のデータ構造をメモリにロードします。

于 2011-03-20T13:37:27.607 に答える
0

辞書内の単語をすばやく検索するために DAWG を使用していると思います。DAWG にはO(LEN)検索の複雑さがあります。

何年も前に、私は J2ME アプリを開発し、同じ問題に直面しました。しかし、その時代の電話は、500K以上の文字列を保存するために、そのようなRAM量のRAMメモリを明確に提供できませんでした)私が使用した解決策は次のとおりです:

  1. すべての単語を読み取り、並べ替え、ファイルに行ごとに入れ、単語ごとに precompute しskipBytesます。- このワードの前のバイト数。skipBytes の計算は簡単です。擬似コードは skipBytes[0]=words[0].bytesLen; for i=1 to n skipBytes[i]=skipBytes[i-1]+words[i].getBytesLength
  2. アプリの起動時に、500k skipBytes を int 配列に読み取ります。500K 文字列よりもはるかに小さい)
  3. dict 内の単語の検索 - 二分検索。array[i]ソートされた配列でそれを実行していると想像してくださいRandomAccessFile.read(skipBytes[i])。Google Java Random Access Files 私の疑似コードはもちろん間違っています。それは単なる方向性です。

複雑さ - O(LEN*LOG(N))= 二分探索の LOG と文字列の比較は、線形の複雑さです。LOG(500000)~19, LEN ~ 最悪の場合の平均単語長は 50 (素晴らしい上限) であるため、検索操作は依然として非常に高速であり、マイクロ秒で実行される操作はわずか 1000 回程度です。利点 - メモリ使用量が少ない。

Web アプリの場合、多くのユーザーが検索を実行する場合LOG(N)は重要になりますが、アプリが 1 人だけにサービスを提供する場合、ループ内で実行されていない場合、LOG(500000) はあまり変化しません)

于 2014-09-11T05:54:36.277 に答える