8

アナグラムと部分一致を見つけるためのモバイルアプリを作成しています。計算能力はそれほど多くなく、効率が重要であるため、モバイルは重要です。

アルゴリズムは、繰り返しを含む任意の数の文字を受け取り、すべての文字を1回だけ使用して、その文字から構成される最長の単語を検索します。私はまた、トップの結果をすばやく見つけることに興味があり、Nが満たされている限り、ボトム（短いもの）にはあまり関心がありません。例えば：

STACK => stack, tacks, acts, cask, cast, cats…

私はいくつかのグーグルを行い、いくつかのアルゴリズムを見つけました。そして、効率的だと思ったものを思いつきましたが、私が望むほど効率的ではありません。

ソートされたキーをそのキーを生成する実際の単語にマップするルックアップ辞書が事前に作成されています。

"aelpp" => ["apple", "appel", "pepla"]

キーの長さに基づいて、各辞書をさらに別の辞書に分割しました。したがって、5文字の長さのキーはある辞書にあり、6文字のキーは別の辞書にあります。これらの各ディクショナリは配列内にあり、インデックスはディクショナリで見つかったキーの長さです。

anagramArray[5] => dictionary5
dictionary5["aelpp"] => ["apple", "appel", "pepla"]

私のアルゴリズムは、入力単語 " lappe"を取得することから始まり、それをソートします。

"lappe" => "aelpp"

ここで、最大5文字の内容を持つ辞書ごとに、比較して引き出します。擬似コードは次のとおりです。

word = input.sort
for (i = word.length; i > 0; i--)
    dictionaryN = array[i]
    for (key in dictionaryN)
        if word matches key
            add to returnArray
        end
    end
    if returnArray count > N
      break
    end
end

returnArray.sort by longest word, alphabetize

辞書には約17万語しか含まれていませんが、12文字の入力で検索に最大20秒かかります。私のmatch方法では、キーから正規表現を作成します。

"ackst" => /a.*c.*k.*s.*t.*/

たとえば、acst（acts）などの4文字のキーは、次のackst理由で（stack）と一致します。

"ackst" matches /a.*c.*s.*t.*/

私は他のアプリがはるかに短い時間で同じことをするのを見てきました、そして私のアプローチがゴミなのか、それとも単に微調整が必​​要なのか疑問に思います。

最大長でソートされた単語から上位N個のアナグラムを生成するための最大の計算効率を得るにはどうすればよいですか？

4

5 に答える 5

6

辞書を文字のツリーと考える（そしておそらく表現する）場合は、多くのノードを見ることを避けることができます。「スタック」が辞書にある場合、ルートからackstというラベルの付いたリーフへのパスがあります。入力単語が「attacks」の場合は、これを並べ替えてaacksttを取得します。ルートからリンクをたどり、aacksttからの文字を消費しながら、再帰ルーチンを作成できます。ackに到達すると、文字列にsttが残っているので、sに従ってackstに到達できますが、uに続いてackuとその子孫に到達し、vに続いてackvとその子孫に到達するなどを除外できます。

実際、このスキームでは、1つのツリーを使用して任意の数の文字の単語を保持できます。これにより、ターゲットの長さごとに1つずつ、複数の検索を実行する手間が省けます。

于 2011-07-02T04:56:54.580 に答える
0

次のように辞書を作成します。

 For each word W in the English language (or whatever word set you have)

     Sort the characters in W by alphabetical order (e.g. "apple" -> "aelpp") into a new string called W'

     Compute Hash H into W' using any fast hash algorithm (e.g CRC32.  You could likely invent anything yourself that has a low number of collisions)

     Store W and H as an element in the dictionary array
     That is:
        Word.original = W;
        Word.hash = Hash(W');
        Dictionary.append(Word);

  Sort the dictionary by hash values.

そして今、すべてのアナグラムを検索するか、単語Sを検索します

  Sort the characters in S by alphabetical order (e.g. "apple" -> "aelpp") into a new string called S'

  Compute Hash H of S' using the same fast hash algorithm above

  Now do a binary search on the dictionary for H.  The binary search should return an index F into Dictionary

  If the binary search fails to return an index into the Dictionary array, exit and return nothing

  I = F

  // Scan forward in the dictionary array looking for matches
  // a matching hash value is not a guarantee of an anagram match
  while (I < Dictionary.size) && (Dictionary[I].hash == H)
       if (IsAnagram(Dictonary[I], S)
           ResultSet.append(Dictionary[I].original)

  // Scan backwards in the dictionary array looking for matches
  I = F-1;
  while (I >= 0) && (Dictionary[I].hash == H)
       if (IsAnagram(Dictonary[I], S)
           ResultSet.append(Dictionary[I].original)


  return ResultSet

ここでは、「サブストリング」検索（検索ワードよりも長さが短いアナグラムワードの検索）の処理方法については説明しませんでした。これが要件である場合は少し混乱しました。あなたの指示は、結果として得られるアナグラムのセットに検索ワードとまったく同じ文字セットですが、検索文字列のすべてのサブ文字列を列挙し、上記の検索アルゴリズムを使用して各サブ文字列を実行できる可能性があります。

于 2011-07-02T05:40:55.373 に答える
0

正規表現の生成には少しコストがかかるため、ループ内で生成することはおそらく望ましくありません。

頭に浮かぶオプション（必ずしも超効率的ではありませんが、この特定の場合に役立つようです）は、辞書内のすべての単語を検索する代わりに、さまざまな組み合わせの文字を削除して、結果の文字列が含まれているかどうかを確認することです。あなたの辞書。これは2^n回の反復（nは単語の文字数）で最大になり、n<18の場合は170kよりも優れています。この特定のアプローチは長い入力には耐えられないことに注意してください。それ以外の場合は非常に高速です。

于 2011-07-02T04:13:53.047 に答える
0

これは単なるアイデアですが、おそらくそれはあなたが探しているものです。繰り返す構造は1つだけで、すべてのサイズのすべての単語が含まれています。反復ステップごとに、もう1つの文字を導入し、すでに導入されている文字よりも「大きい」文字を持たない単語のみに検索を絞り込みます。たとえば、Mを導入すると、NZの範囲内には何も導入できなくなります。

構造は、1文字の導入により、さらにいくつかのツリーレベルにつながる二分木である可能性があります。各ノードには文字があり、残りの小さい文字に分岐し、残りの大きい文字に分岐し、次の絞り込み検索のルートに分岐し、文字で完全に構築された単語のリストへのポインタがありますこれまでに紹介されました。その検索サブスペースに可能な単語がない場合、ブランチはnullになる可能性がありますが、同時に3つのブランチに対してnullを設定し、単語のリストへのポインターとしてnullを設定することはできません。（まあ、今は関係のない一種の最適化として、あなたはそうすることができます）。単語のリストへのポインタの代わりに、特定の文字を含む単語の存在を示すフラグを設定できますが、それらの単語は他の辞書に保存できます。

それで、ACKSTという文字があるとしましょう。構造体のルートから、ループ内のこれらすべての文字を検索しますが、たとえばKの後は、AとCでのみ検索を続行できます（SとTはKより上にあるため）。最大の単語に最も関心があるため、最大の文字（この場合はT）から検索を開始し、次に大きい文字で検索を続行する必要があります。CATという単語に対しては、特定の順序で文字T、C、Aを検索することしかできません。そのAに到達すると、次の単語のリストへのポインタが表示されます：ACT、CAT。

于 2011-07-02T09:38:39.437 に答える
-1

2つの文字列がアナグラムであるかどうかを確認するためのO（N）時間とO（1）ソリューション

bool Anagram( const  char *s1, const char *s2)
{
    unsigned int sum=0;

    if ( s1 == NULL || s2 == NULL)
        return false;

    while ( *s1 != '\0' && s2 != '\0')
    {
                   sum ^= *s1;
                   sum ^= *s2;
                   s1++;
                   s2++;
    }

    if ( s1 != '\0' || s2 != '\0')
        return false;

    if (sum) return false;

    return true;
}

2つの等しい数を排他的論理和する場合..結果は0です。（したがって、アルゴリズム）

于 2015-05-04T14:48:12.137 に答える