0

T9 辞書はどのように機能しますか? その背後にあるデータ構造は何ですか。例: 16 語 (すべて大文字) のリスト/辞書があります。数字で入力を与え、対応する出力は辞書の数字と一致する単語である必要があります.C/C++/JAVAでこれを実装する方法.[また、単語がリストに追加された場合もサポートする必要があります]

2:A/B/C
3:D/E/F
4:G/H/I
5:J/K/L
6:M/N/O
7:P/Q/R/S
8:T/U/V
9:W/X/Y/Z

LIST{DRAWING,PAINTING,DANCE.....}

出力ウィンドウの例:

Input : 3729464
output : DRAWING
4

2 に答える 2

1

完全な単語を単純に直接検索するだけで十分な場合は、単語の文字を対応する数字に置き換える関数を作成するのが最適です。

A,B,C  -> 2
D,E,F  -> 3

等

次に、その関数をすべての辞書エントリに適用し、結果をキーとして保存しますが、元の形式はハッシュ テーブル (または同様のデータ構造) の値として保存します。各数字は複数の異なる文字を表すことができるため、同じキーを複数の値にマップする必要がある場合があります。文字列のリストを値の型として使用できます。

entries(3829464)  = [DRAWING]
entries(72468464) = [PAINTING]
entries(843)      = [THE,TIE]

等々。

次に、ハッシュのキーに対して直接、指定された入力数字シーケンスを検索し、既製のリストとしてすべての候補を簡単に取得できます。

実際の T9 関数は、継続もサポートしています。一連の数字を入力し、入力シーケンスの可能な継続である可能性のあるすべての文字列を取得します。そのためには、検索トライが優れたデータ構造です。繰り返しになりますが、文字変換の結果として得られる数字は、トライの遷移ラベルとして最適に使用され、文字列の元の形式は受け入れ状態に最適に格納されます。特定のノードの下のサブトライで見つかった受け入れ状態の総数など、追加情報を内部ノードに保存することができます。これは、すべての継続候補を取得するためにサブトライのトラバースを開始するか、ユーザーからさらに入力が与えられるまで待機するかを O(1) 時間で決定するのに役立ちます。

于 2012-09-10T08:41:48.997 に答える