1

リストがあります (>50,000 語)。リスト内の各単語には、一連のエイリアスが関連付けられています。各単語には、平均して 5 つの別名があります。

平均して 6 語の入力文字列を取得します。私がしなければなりません：

// Pseudocode 
foreach word in input_string
    if word == x  or  word in alias(x) // x is a word in the list
       tag (word, x)  // Tag word with x
    else 
       tag (word, 0)
end

上記のルックアップの高速実行を可能にするエイリアスのリストを維持するための高速データ構造は何ですか?

4

1 に答える 1

3

O(n/k) または O(log n) ルックアップによる連想構造が適切です。

例は次のとおりです。

于 2012-05-23T17:03:30.130 に答える