algorithm - 特定の単語のアナグラムを見つける

Question

2 つの単語のうちの 1 つが別の単語とまったく同じ文字を持っている場合、2 つの単語はアナグラムです。

例 : Anagram&Nagaramはアナグラムです (大文字と小文字を区別しません)。

現在、これに似た多くの質問があります。2 つの文字列がアナグラムであるかどうかを調べるには、次の 2 つの方法があります。

1) Sort文字列を比較します。

2)これらの文字列のを作成し、frequency mapそれらが同じかどうかを確認します。

しかし、この場合、単語が与えられ (簡単にするために、単一の単語のみを想定し、単一の単語のアナグラムのみを持つことにします)、そのためのアナグラムを見つける必要があります。

私が念頭に置いている解決策は、単語のすべての順列を生成し、これらの単語のどれが辞書に存在するかを確認できるということです。しかし明らかに、これは非常に非効率的です。はい、辞書もご利用いただけます。

では、ここにはどのような選択肢がありますか?

私はまた、何かを使用して何かを行うことができるという同様のスレッドを読みましたTriesが、その人は、アルゴリズムが何であるか、なぜ最初にTrieを使用したのかについて説明しませんでした.PythonまたはRubyでも実装が提供されただけです. それはあまり役に立たなかったので、この新しいスレッドを作成しました。実装 (C、C++、または Java 以外) を共有したい場合は、それについても説明してください。

score 76 · Accepted Answer

アルゴリズムの例:

Open dictionary
Create empty hashmap H
For each word in dictionary:
  Create a key that is the word's letters sorted alphabetically (and forced to one case)
  Add the word to the list of words accessed by the hash key in H

特定の単語のすべてのアナグラムを確認するには:

Create a key that is the letters of the word, sorted (and forced to one case)
Look up that key in H
You now have a list of all anagrams

ビルドが比較的速く、ルックアップが非常に高速です。

score 19 · Accepted Answer

私は推測する新しい解決策を思いつきました。これは、算術の基本定理を使用します。つまり、最初の 26 個の素数の配列を使用するという考え方です。次に、入力単語の各文字に対して、対応する素数 A = 2、B = 3、C = 5、D = 7 … を取得し、入力単語の積を計算します。次に、辞書内の各単語に対してこれを行い、単語が入力単語と一致する場合、それを結果のリストに追加します。すべてのアナグラムは同じ署名を持ちます。

1より大きい整数は素数であるか、素数の一意の積として記述できます(順序は無視されます)。

これがコードです。単語を大文字に変換すると、65 が最初の素数に対応する A の位置になります。

private int[] PRIMES = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,
        37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103,
        107, 109, 113 };

これは方法です：

 private long calculateProduct(char[] letters) {
    long result = 1L;
    for (char c : letters) {
        if (c < 65) {
            return -1;
        }
        int pos = c - 65;
        result *= PRIMES[pos];
    }
    return result;
}

score 2 · Accepted Answer

2 つの単語の長さが同じでない場合、それらはアナグラムではないことがわかっています。したがって、同じ長さの単語のグループに辞書を分割できます。

ここで、これらのグループの 1 つだけに注目します。基本的に、この小さな宇宙ではすべての単語がまったく同じ長さです。

各文字の位置が次元であり、その次元の値が文字 (ASCII コードなど) に基づいている場合。次に、単語ベクトルの長さを計算できます。

たとえば、'A'=65、'B'=66、そしてlength("AB") = sqrt(65*65 + 66*66). 明らかに、length("AB") = length("BA").

明らかに、2 つの単語がアナグラムである場合、それらのベクトルの長さは同じです。次の質問は、2 つの単語 (文字数が同じ) のベクトルが同じ長さの場合、それらはアナグラムですか? その長さのすべてのベクトルが球を形成するため、多くのベクトルが存在するため、直感的にはノーと言えます。この場合は整数空間にいるため、実際にいくつあるかはわかりません。

しかし、少なくとも辞書をさらに分割することができます。辞書の各単語について、ベクトルの距離を計算します。 for(each letter c) { distance += c*c }; distance = sqrt(distance);

次に、長さのすべての単語のマップを作成nし、距離でキーを設定します。値は、nその特定の距離を生成する長さの単語のリストです。

距離ごとにマップを作成します。

次に、ルックアップは次のアルゴリズムになります。

単語の長さに基づいて正しい辞書マップを使用する
単語のベクトルの長さを計算します
その長さに一致する単語のリストを検索します
リストを調べて、単純なアルゴリズムを使用してアナグラムを選択すると、候補のリストが大幅に削減されます

score 1 · Accepted Answer

static void Main(string[] args)
{

    string str1 = "Tom Marvolo Riddle";
    string str2 = "I am Lord Voldemort";

    str2=  str2.Replace(" ", string.Empty);
    str1 = str1.Replace(" ", string.Empty);
    if (str1.Length != str2.Length)
        Console.WriteLine("Strings are not anagram");
    else
    {
        str1 = str1.ToUpper();
        str2 = str2.ToUpper();
        int countStr1 = 0;
        int countStr2 = 0;
        for (int i = 0; i < str1.Length; i++)
        {
            countStr1 += str1[i];
            countStr2 += str2[i];

        }
        if(countStr2!=countStr1)
            Console.WriteLine("Strings are not anagram");
        else Console.WriteLine("Strings are  anagram");

    }
    Console.Read();
}

score 1 · Accepted Answer

Well Tries を使用すると、単語が存在するかどうかを簡単に確認できます。したがって、辞書全体を試してみると、次のようになります。

http://en.wikipedia.org/wiki/Trie

その後、あなたの言葉を取り、文字を取り、残りの文字の任意の組み合わせでトライを「歩く」ことができるかどうかを再帰的にチェックすることで、簡単なバックトラックを行うことができます（一度に1文字追加します）。すべての文字が再帰分岐で使用され、Trie に有効なパスがあった場合、その単語は存在します。

Trie は適切な停止条件として役立ちます。文字列の一部、たとえば "Anag" が Trie 内の有効なパスであるかどうかを確認できます。そうでない場合は、その特定の再帰分岐を中断できます。これは、文字のすべての順列をチェックする必要がないことを意味します。

疑似コードで

checkAllChars(currentPositionInTrie, currentlyUsedChars, restOfWord)
    if (restOfWord == 0)
    {
         AddWord(currentlyUsedChar)
    }
    else 
    {
        foreach (char in restOfWord)
        {
            nextPositionInTrie = Trie.Walk(currentPositionInTrie, char)
            if (nextPositionInTrie != Positions.NOT_POSSIBLE)
            {
                checkAllChars(nextPositionInTrie, currentlyUsedChars.With(char), restOfWord.Without(char))
            }
        }   
    }

明らかに、ツリーを段階的に「ウォーク」し、次のノードへの指定された文字を持つパスがあるかどうかを各ノードで確認できる素敵なTrieデータ構造が必要です...

score 0 · Accepted Answer

それはあなたがあなたの辞書をどのように保存するかに依存します。単純な単語の配列の場合、線形より高速なアルゴリズムはありません。

並べ替えられている場合は、これが機能する可能性のあるアプローチです。私はちょうど今それを発明しました、しかし私はそれが線形アプローチより速いと思います。

辞書をD、現在のプレフィックスをSとして示します。S= 0;
単語の頻度マップを作成します。それをFで表します。
二分探索を使用して、辞書内の各文字の先頭にポインタを見つけます。このポインタの配列をPで表します。
AからZまでの各文字cについて、F [c] == 0の場合はスキップし、それ以外の場合はスキップします。
- S + = c;
- F [c]-;
- P<-すべての文字に対してiP[i] = S+iで始まる最初の単語へのポインタ。
- 単語に一致するものが見つかるまで、またはそのような一致が存在しないことがわかるまで、ステップ4を再帰的に呼び出します。

とにかく、これは私がそれをする方法です。より一般的なアプローチがあるはずですが、これは線形よりも高速です。

score 0 · Accepted Answer

すべての順列を生成するのは簡単ですが、辞書でそれらの存在を確認することは「非常に非効率的」な部分であると心配していると思います。しかし、それは実際には、辞書に使用するデータ構造によって異なります。もちろん、単語のリストはユースケースには非効率的です。Triesといえば、おそらく理想的な表現であり、非常に効率的でもあります。

もう 1 つの可能性は、辞書に対して何らかの前処理を行うことです。たとえば、キーがソートされた単語の文字であり、値が単語のリストであるハッシュテーブルを作成します。このハッシュテーブルをシリアル化して、ファイルに書き込んで後ですばやくリロードすることもできます。次に、アナグラムを検索するには、指定された単語を並べ替えて、ハッシュテーブル内の対応するエントリを検索します。

score 0 · Accepted Answer

ハッシュマップソリューションを実装しようとしました

public class Dictionary {

    public static void main(String[] args){

    String[] Dictionary=new String[]{"dog","god","tool","loot","rose","sore"};

    HashMap<String,String> h=new HashMap<String, String>();

    QuickSort q=new QuickSort();

    for(int i=0;i<Dictionary.length;i++){

        String temp =new String();

        temp= q.quickSort(Dictionary[i]);//sorted word e.g dgo for dog

        if(!h.containsKey(temp)){
           h.put(temp,Dictionary[i]);
        }

        else
        {
           String s=h.get(temp);
           h.put(temp,s + " , "+ Dictionary[i]);
        }
    }

    String word=new String(){"tolo"};

    String sortedword = q.quickSort(word);

    if(h.containsKey(sortedword.toLowerCase())){ //used lowercase to make the words case sensitive

        System.out.println("anagrams from Dictionary   :  " + h.get(sortedword.toLowerCase()));
    }

}

score -3 · Accepted Answer

1つの解決策は - 素数をアルファベット文字にマップし、素数を掛ける

For ex - 

    a -> 2
    b -> 3
    ......
    .......
    ......
    z -> 101

そう

'ab' -> 6
'ba' -> 6
'bab' -> 18
'abba' -> 36
'baba' -> 36

指定された単語の MUL_number を取得します。指定された単語と同じ MUL_number を持つ辞書からすべての単語を返します

algorithm - 特定の単語のアナグラムを見つける

13 に答える 13

Related

Reference