7

基本的に、アナグラムは文字列の順列のようなものです。たとえばstack、sackt、 、stakcすべてのアナグラムですstack(上記の単語は意味がありません)。とにかく、私が基本的に何を意味するかを理解できたはずです。

今、私はanagrams与えられた百万語のリストが欲しいか、単に辞書から言います。

私の基本的な質問はFind total number of unique anagrams in a dictionary?

時間の複雑さがかなり悪いため、並べ替えと比較は機能しません。

ハッシュテーブル、文字列をキーとして使用することを考えました。

しかし問題は、ハッシュ関数はどうあるべきか? 擬似コードが提供されると役立ちます。言及されたアプローチよりも優れた他のアプローチも役立ちます。

ありがとう。

4

5 に答える 5

24

明らかな解決策は、各文字を素数にマップし、素数を乗算することです。したがって、'a'' -> 2 および 'b'' -> 3 の場合、

  • 'ab' -> 6
  • 「ば」 -> 6
  • 「バブ」 -> 18
  • 'アバ' -> 36
  • 「ババ」 -> 36

オーバーフローの可能性を最小限に抑えるために、最小の素数をより頻繁な文字 (e、t、i、a、n) に割り当てることができます。注: 26 番目の素数は 101 です。

更新: 実装はここにあります

于 2012-06-20T10:07:19.440 に答える
2

考えられるハッシュ関数の 1 つは、(英単語のみを想定して) 各文字の出現回数のソートされたカウントです。したがって、「アナグラム」の場合、[('a', 3), ('g', 1), ('n', 1), ('m', 1), ('r',1)] を生成します。

または、単語からビットマスクを生成することで、不正確なグループ化を取得できます。ビット 0 ～ 25 の各ビットは、その文字の有無を表します (ビット 0 は「a」を表し、ビット 25 は「z」を表します)。ただし、ハッシュされた各グループをさらに分割して、「to」と「to」などを区別するために、もう少し処理を行う必要があります。

これらのアイデアは役に立ちますか? 特定の実装言語を念頭に置いていますか (C++、Python、または Scala を実行できます)。

編集:Scalaコードと出力の例をいくつか追加しました:

OK: 私は現在 Scala モードにいるので、あなたが求めていることを実行するために何かをノックアップしましたが、(エヘム) Scala や関数型プログラミングに精通していない場合は、あまり明確ではないかもしれません.

ここから英単語の大きなリストを使用します: http://scrapmaker.com/data/wordlists/twelve-dicts/2of12.txt

この Scala コードを実行します (スクリプト モードで Scala 2.9 を使用すると、約 40,000 語の辞書をコンパイルする時間を含めて約 5 秒かかります。最も効率的なコードではありませんが、最初に頭に浮かんだことです)。

// Hashing function to go from a word to a sorted list of letter counts
def toHash(b:String) = b.groupBy(x=>x).map(v => (v._1, v._2.size) ).toList.sortWith(_._1 < _._1)


// Read all words from file, one word per line
val lines = scala.io.Source.fromFile("2of12.txt").getLines

// Go from list of words to list of (hashed word, word)
val hashed = lines.map( l => (toHash(l), l) ).toList

// Group all the words by hash (hence group all anagrams together)
val grouped = hashed.groupBy( x => x._1 ).map( els => (els._1, els._2.map(_._2)) )

// Sort the resultant anagram sets so the largest come first
val sorted = grouped.toList.sortWith( _._2.size > _._2.size )

for ( set <- sorted.slice(0, 10) )
{
    println( set._2 )
}

これにより、アナグラムの最初の 10 セット (最初にメンバーが最も多いセット) がダンプされます。

List(caret, cater, crate, react, trace)
List(reins, resin, rinse, risen, siren)
List(luster, result, rustle, sutler, ulster)
List(astir, sitar, stair, stria, tarsi)
List(latrine, ratline, reliant, retinal)
List(caper, crape, pacer, recap)
List(merit, miter, remit, timer)
List(notes, onset, steno, stone)
List(lair, liar, lira, rail)
List(drawer, redraw, reward, warder)

これは、より複雑なビットマスク方式ではなく、最初の提案 (文字数のリスト) を使用することに注意してください。

編集 2: ハッシュ関数を各単語の文字の単純な並べ替え (JAB で提案されているように) に置き換えて、より明確で高速なコードで同じ結果を得ることができます。

def toHash(b:String) = b.toList.sortWith(_<_)
于 2012-06-19T20:17:21.730 に答える
1

各文字のハッシュコード値をXORし、結果を入力長でXORすると、単語の順序に関係なく同じ値が得られます。つまり、すべてのアナグラムが同じハッシュを生成します。（長さによるXORは、それ自体に対する's'のハッシュが常に0であるため、'boss'と'bo'が同じ値を返すことを防ぎます。）

例：

int AnagramHash(string input)
{
    int output = 0;

    foreach(char c in input)
        output ^= c.GetHashCode();

    return output ^ input.Length;
}

同じAnagramHashですべての単語を検索する必要があります。全体的な計算を減らすために、（アルゴリズムに関係なく）ハッシュのフィールドでディクショナリテーブルを更新します。

編集：また、補足として、XORはALUによって実行される最も単純な操作であるため、XORを使用することになった場合は、ハッシュをかなり迅速に生成できるはずです。

于 2012-06-19T20:33:06.700 に答える
0

文字列をキーとして、list(string) を値として持つハッシュマップを使用します。文字列のリストには、キー文字列のすべてのアナグラムが含まれます。

質問は「ファイル内の単語のすべてのアナグラムを見つける」に似ています

ここでアルゴとコードを表示http://justprogrammng.blogspot.com/2012/06/determine-anagrams-of-word-in-file.html

于 2012-06-22T15:52:00.883 に答える
0

時間の複雑さがかなり悪いため、並べ替えと比較は機能しません。

時間の複雑さを余分なメモリと交換して、単語の文字数を 26 文字char(または使用している言語に相当するもので、ローマ字とアルファベット文字のみを使用していると仮定) の配列とハッシュに格納するだけです。配列。単語の長さに対して O(n) 時間で行き詰まっていますが、ほとんどの英単語はそれほど長くはありません。

たとえばstack、、sacktおよびはすべて、、、、、== 1の位置と残りのすべてが 0 に設定されたstakc配列を持ちます。stack

コメントに基づいて、単語自体を並べ替えない限り、単語の文字を並べ替えても問題ないことを意味します。アレックスの答えよりも簡単なことをして、単語の文字列とハッシュの文字を並べ替えるだけです。結果。（larsmansは最初に言ったが、答えとして投稿しなかったので...）

于 2012-06-19T20:18:59.390 に答える