Oxford English Dictionaryを設計する

Oxford English Dictionaryをどのようにデザインするかは、インタビューで尋ねられました。Oxford English Dictionaryを設計する

私はTREEデータ構造を使用すると言ったが、彼はそれは多くのメモリを必要とすると答えた。どのような他のデータ構造を使うべきですか？

2011-12-10 AKIWEB

Oxford English Dictionaryは、世界を別の単語にマッピングする代わりに使用しますいくつかの文章の単語の意味？そのような場合、コーディングする単語はあなたの問題の中で最も少なく、意味のもの（文法などの単語）を表すことを考えたり、LHARCのような辞書ベースのパッキングを検討したりするべきです。あなたにとってラッキーな英語はこのようにあまり複雑ではありません... – Spektre

私はT9辞書を格納するために、携帯電話で過去に使用された聞い

1つのデータ構造がある（まあ、これが唯一の重要な問題に対処し、ではなく定義記憶）以下：

エントリがソートされており、各エントリは、継続すべき位置からの前のエントリへのオフセットで開始する必要があり、継続も継続する必要があります。たとえば：

apple 
4icable 
7tion

はリンゴ、適用、アプリケーションにデコードします。しかし、これは

appl -> e 
    -> ica -> ble 
      -> tion

参照、マージされた鎖を有する試行と大差ないかもしれないウィキペディアは言葉が同じサフィックスを持って、それだけではない枝が、枝がマージすることができ、木、異なっている、Directed acyclic word graphを発見しました。これは確かに優れたストレージになる可能性があります。他の人のよう

 a 
    /\ 
    pplic utom 
     \/
     ation

出典

2011-12-10 01:18:48 ron

ところで、ウィキペディアは「辞書の単語を保存するだけであれば、最小限の非周期的な決定論的有限オートマトンはトライよりも少ないスペースしか使用しません」と言いました。答えに追加されました。 – ron

多くのメモリを使用しません。あなたの答えは良かった。おそらく1995年です。自分自身を幸運に考えてください。

出典

2011-12-10 01:05:34 jmacinnes

うまく設計されたトライのための十分な屋根がない場合、おそらくどちらか、インデックスの他の種類の余地がないが、言及しています。これはインタビューの質問に関するものなので、Bツリーのような古典的なアウト・オブ・コアのデータ構造にあなたを導いているように思えます。

「このデータ構造に対してどのような操作を行いたいのか、どんな種類のパフォーマンスが必要なのか」などの詳細な情報を求めるのが良い回答でした。スペルチェックが必要な場合は、Bloomフィルタが最も効率的な "データ構造"です...

出典

2011-12-10 01:29:37 comingstorm

Oxford English Dictionaryを設計する

答えて

関連する問題