12

たとえば、入力文字列がhelloworldの場合、出力を次のようにします。

do
he
we
low
hell
hold
roll
well
word
hello
lower
world
...

helloworldのサブストリングのアナグラムである最長の単語までずっと。たとえばスクラブルのように。入力文字列は任意の長さにすることができますが、16文字を超えることはめったにありません。

私は検索を行い、トライのような構造を考え出しましたが、実際にこれを行う方法がまだわかりません。

4

8 に答える 8

14

有効なエントリの辞書を保持するために使用される構造は、効率に大きな影響を与えます。それをツリーとして編成します。ルートは単数のゼロ文字「word」、空の文字列です。ルートの各子は、可能な単語の1つの最初の文字であり、それらの子は、可能な単語の2番目の文字であるなどであり、各ノードは、実際に単語を形成するかどうかについてマークされます。

テスター関数は再帰的になります。ゼロ文字で始まり、有効なエントリのツリーから「」は単語ではないが子が含まれていることがわかります。そのため、開始単語（文字なし）に使用可能な残りの各文字を追加して、テスターを再帰的に呼び出します。入力文字列（その時点ですべてです）。有効な場合は、ツリー内の各1文字のエントリを確認してください。子の場合は、残りの使用可能な各文字を追加するテスター関数を再度呼び出します。

したがって、たとえば、入力文字列が「helloworld」の場合、最初に「」を使用して再帰テスター関数を呼び出し、残りの使用可能な文字「helloworld」を2番目のパラメーターとして渡します。関数は、「」が単語ではないことを認識しますが、子「h」は存在します。したがって、「h」と「elloworld」で自分自身を呼び出します。関数は、「h」が単語ではないことを認識しますが、子「e」は存在します。それで、それは「彼」と「lloworld」でそれ自身を呼びます。関数は「e」がマークされていることを確認するので、「彼」は単語です。注意してください。さらに、子「l」が存在するため、次の呼び出しは「loworld」を使用した「hel」です。次に「地獄」、次に「こんにちは」を見つけ、次にバックアウトして、おそらく次に「中空」を見つける必要があります。

于 2009-05-19T01:38:29.593 に答える
9

私は自分の実装に抵抗できませんでした。すべての文字をアルファベット順に並べ替え、それらから作成できる単語にマッピングすることで辞書を作成します。これはO（n）の起動操作であり、すべての順列を見つける必要がありません。辞書を別の言語のトライとして実装して、より高速化することができます。

「getAnagrams」コマンドもO（n）操作であり、辞書内の各単語を検索して、それが検索のサブセットであるかどうかを確認します。getAnagrams（ "radiotelegraphically"） "（20文字の単語）を実行すると、ラップトップで約1秒かかり、1496個のアナグラムが返されました。

# Using the 38617 word dictionary at 
# http://www.cs.umd.edu/class/fall2008/cmsc433/p5/Usr.Dict.Words.txt
# Usage: getAnagrams("helloworld")

def containsLetters(subword, word):
    wordlen = len(word)
    subwordlen = len(subword)

    if subwordlen > wordlen:
        return False

    word = list(word)
    for c in subword:
        try:
            index = word.index(c)
        except ValueError:
            return False
        word.pop(index)
    return True

def getAnagrams(word):
    output = []
    for key in mydict.iterkeys():
        if containsLetters(key, word):
            output.extend(mydict[key])

    output.sort(key=len)
    return output

f = open("dict.txt")
wordlist = f.readlines()
f.close()

mydict = {}
for word in wordlist:
    word = word.rstrip()
    temp = list(word)
    temp.sort()
    letters = ''.join(temp)

    if letters in mydict:
        mydict[letters].append(word)
    else:
        mydict[letters] = [word]

実行例：

>>> getAnagrams("helloworld")
>>> ['do', 'he', 'we', 're', 'oh', 'or', 'row', 'hew', 'her', 'hoe', 'woo', 'red', 'dew', 'led', 'doe', 'ode', 'low', 'owl', 'rod', 'old', 'how', 'who', 'rho', 'ore', 'roe', 'owe', 'woe', 'hero', 'wood', 'door', 'odor', 'hold', 'well', 'owed', 'dell', 'dole', 'lewd', 'weld', 'doer', 'redo', 'rode', 'howl', 'hole', 'hell', 'drew', 'word', 'roll', 'wore', 'wool','herd', 'held', 'lore', 'role', 'lord', 'doll', 'hood', 'whore', 'rowed', 'wooed', 'whorl', 'world', 'older', 'dowel', 'horde', 'droll', 'drool', 'dwell', 'holed', 'lower', 'hello', 'wooer', 'rodeo', 'whole', 'hollow', 'howler', 'rolled', 'howled', 'holder', 'hollowed']
于 2009-05-19T07:13:19.577 に答える
6

必要なデータ構造は有向非巡回ワードグラフ（dawg）と呼ばれ、AndrewAppelとGuyJacobsenの論文「TheWorld'sFastest Scrabble Program」で説明されていますが、残念ながら、オンラインで無料で利用できないようにしています。ACMメンバーシップまたは大学図書館があなたに代わってそれを取得します。

私はこのデータ構造を少なくとも2つの言語で実装しました---シンプルで、実装が簡単で、非常に高速です。

于 2009-05-19T02:25:49.997 に答える
2

必要なのは、べき集合の実装です。

Eric Lippartsのブログも見てください。彼は、少し前にこのことについてブログに書いています。

編集：

これは、与えられた文字列からパワーセットを取得するために私が書いた実装です...

private IEnumerable<string> GetPowerSet(string letters)
{
  char[] letterArray = letters.ToCharArray();
  for (int i = 0; i < Math.Pow(2.0, letterArray.Length); i++)
  {
    StringBuilder sb = new StringBuilder();
    for (int j = 0; j < letterArray.Length; j++)
    {
      int pos = Convert.ToInt32(Math.Pow(2.0, j));
      if ((pos & i) == pos)
      {
        sb.Append(letterArray[j]);
      }
    }
    yield return new string(sb.ToString().ToCharArray().OrderBy(c => c).ToArray());
  }
}

この関数は、渡された文字列を構成するcharのべき集合を提供し、アナグラムの辞書へのキーとしてこれらを使用できます...

Dictionary<string,IEnumerable<string>>

私はそのようなアナグラムの辞書を作成しました...（おそらくもっと効率的な方法がありますが、これは単純で、スクラブルトーナメントの単語リストで十分に迅速でした）

wordlist = (from s in fileText.Split(new string[] { Environment.NewLine }, StringSplitOptions.RemoveEmptyEntries)
                let k = new string(s.ToCharArray().OrderBy(c => c).ToArray())
                group s by k).ToDictionary(o => o.Key, sl => sl.Select(a => a));
于 2009-05-19T01:26:39.697 に答える
2

単純なアプローチは、すべての「サブストリング」を生成し、それらのそれぞれについて、それが受け入れ可能な単語のセットの要素であるかどうかを確認することです。たとえば、Python 2.6の場合：

import itertools
import urllib

def words():
  f = urllib.urlopen(
    'http://www.cs.umd.edu/class/fall2008/cmsc433/p5/Usr.Dict.Words.txt')
  allwords = set(w[:-1] for w in f)
  f.close()
  return allwords

def substrings(s):
  for i in range(2, len(s)+1):
    for p in itertools.permutations(s, i):
      yield ''.join(p)

def main():
  w = words()
  print '%d words' % len(w)
  ss = set(substrings('weep'))
  print '%d substrings' % len(ss)
  good = ss & w
  print '%d good ones' % len(good)
  sgood = sorted(good, key=lambda w:(len(w), w))
  for aword in sgood:
    print aword

main()

放出します：

38617 words
31 substrings
5 good ones
we
ewe
pew
wee
weep

もちろん、他の回答が指摘しているように、データを意図的に整理すると、ランタイムを大幅に高速化できます-高速アナグラムファインダーに最適なデータ編成はかなり異なる可能性があります...しかし、それは辞書の性質に大きく依存します許可された単語の数（ここのように数万、または数百万？）。ハッシュマップと「署名」（各単語の文字の並べ替えに基づく）、および試行＆cを検討する必要があります。

于 2009-05-19T01:50:24.780 に答える
0

この質問への回答にあるRubyコードも問題を解決すると思います。

于 2009-05-19T03:28:27.407 に答える
0

Tim Jのように、EricLippertのブログ投稿で最初に頭に浮かぶことがあります。私は彼が彼の最初の試みのパフォーマンスを改善する方法についてのフォローアップを書いたことを付け加えたいと思いました。

于 2009-05-19T01:41:42.787 に答える
0

私は最近携帯電話でたくさんのWordfeudをプレイしていて、可能な単語のリストを提供するコードを考え出すことができるかどうか興味がありました。次のコードは、使用可能なソース文字（ワイルドカードの場合は*）と、許可される単語のマスターリスト（TWL、SOWPODSなど）を含む配列を取得し、一致するリストを生成します。これは、ソース文字からマスターリストの各単語を作成しようとすることで行われます。

コードを書いた後でこのトピックを見つけました。JohnPirieのメソッドやDAWGアルゴリズムほど効率的ではありませんが、それでもかなり高速です。

public IList<string> Matches(string sourceLetters, string [] wordList)
{
    sourceLetters = sourceLetters.ToUpper();

    IList<string> matches = new List<string>();

    foreach (string word in wordList)
    {
        if (WordCanBeBuiltFromSourceLetters(word, sourceLetters))
            matches.Add(word);
    }

    return matches;
}


public bool WordCanBeBuiltFromSourceLetters(string targetWord, string sourceLetters)
{
    string builtWord = "";

    foreach (char letter in targetWord)
    {
        int pos = sourceLetters.IndexOf(letter);
        if (pos >= 0)
        {
            builtWord += letter;
            sourceLetters = sourceLetters.Remove(pos, 1);
            continue;
        }


        // check for wildcard
        pos = sourceLetters.IndexOf("*");
        if (pos >= 0)
        {
            builtWord += letter;
            sourceLetters = sourceLetters.Remove(pos, 1);
        }


    }

    return string.Equals(builtWord, targetWord);

}
于 2011-01-26T21:25:43.790 に答える