アナグラムを生成するための最良の戦略は何でしょうか。
An anagram is a type of word play, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once; ex.
- イレブンプラス2は12プラス1のアナグラムです
- 小数点は、私がドットであるというアナグラムです。
- 天文学者は月のスターのアナグラムです
最初は、文字をごちゃ混ぜにしてすべての可能な組み合わせを生成するだけで、簡単に見えます。しかし、辞書にある単語だけを生成するための効率的なアプローチは何でしょうか。
私はこのページに出くわしました、Rubyでアナグラムを解きます。
しかし、あなたの考えは何ですか？
これらの答えのほとんどはひどく非効率的であり、および/または一言の解決策しか与えません（スペースなし）。私のソリューションは任意の数の単語を処理し、非常に効率的です。
必要なのはトライデータ構造です。これが完全なPython実装です。必要なのは、という名前のファイルに保存された単語リストだけですwords.txt 。ここでスクラブル辞書の単語リストを試すことができます。
http://www.isc.ro/lists/twl06.zip
MIN_WORD_SIZE = 4 # min size of a word in the output
class Node(object):
def __init__(self, letter='', final=False, depth=0):
self.letter = letter
self.final = final
self.depth = depth
self.children = {}
def add(self, letters):
node = self
for index, letter in enumerate(letters):
if letter not in node.children:
node.children[letter] = Node(letter, index==len(letters)-1, index+1)
node = node.children[letter]
def anagram(self, letters):
tiles = {}
for letter in letters:
tiles[letter] = tiles.get(letter, 0) + 1
min_length = len(letters)
return self._anagram(tiles, [], self, min_length)
def _anagram(self, tiles, path, root, min_length):
if self.final and self.depth >= MIN_WORD_SIZE:
word = ''.join(path)
length = len(word.replace(' ', ''))
if length >= min_length:
yield word
path.append(' ')
for word in root._anagram(tiles, path, root, min_length):
yield word
path.pop()
for letter, node in self.children.iteritems():
count = tiles.get(letter, 0)
if count == 0:
continue
tiles[letter] = count - 1
path.append(letter)
for word in node._anagram(tiles, path, root, min_length):
yield word
path.pop()
tiles[letter] = count
def load_dictionary(path):
result = Node()
for line in open(path, 'r'):
word = line.strip().lower()
result.add(word)
return result
def main():
print 'Loading word list.'
words = load_dictionary('words.txt')
while True:
letters = raw_input('Enter letters: ')
letters = letters.lower()
letters = letters.replace(' ', '')
if not letters:
break
count = 0
for word in words.anagram(letters):
print word
count += 1
print '%d results.' % count
if __name__ == '__main__':
main()
プログラムを実行すると、単語がメモリ内のトライにロードされます。その後、検索したい文字を入力するだけで、結果が出力されます。すべての入力文字を使用した結果のみが表示され、それより短いものは表示されません。
出力から短い単語をフィルタリングします。そうでない場合、結果の数は膨大になります。設定を自由に調整してMIN_WORD_SIZEください。が1の場合、入力として「天文学者」を使用するだけで233,549の結果が得られることに注意してMIN_WORD_SIZEください。おそらく、より一般的な英語の単語のみを含む短い単語リストを見つけることができます。
また、辞書に「im」を追加MIN_WORD_SIZEして2に設定しない限り、短縮形「I'm」（例の1つから）は結果に表示されません。
複数の単語を取得する秘訣は、検索で完全な単語に遭遇するたびに、トライのルートノードに戻ることです。次に、すべての文字が使用されるまで、トライをトラバースし続けます。
辞書の各単語について、文字をアルファベット順に並べ替えます。したがって、「foobar」は「abfoor」になります。
次に、入力アナグラムが入ったら、その文字も並べ替えてから調べます。 ハッシュテーブルルックアップと同じくらい高速です！
複数の単語の場合は、並べ替えた文字を組み合わせて、並べ替えることができます。すべての組み合わせを生成するよりもはるかに高速です。
（詳細な最適化と詳細についてはコメントを参照してください）
ワシントン大学 CSE 部門からのこの割り当てを参照してください。
基本的に、単語内の各文字の数だけを持つデータ構造があります (ASCII では配列が機能し、Unicode サポートが必要な場合はマップにアップグレードしてください)。これらの文字セットのうち 2 つを差し引くことができます。カウントが負の場合、ある単語が別の単語のアナグラムになることはできないことがわかります。
前処理:
各葉を既知の単語として、アルファベット順に並べたトライを作成します。
検索時:
入力文字列をマルチセットと見なします。深さ優先検索のようにインデックス トライをトラバースして、最初のサブワードを見つけます。各ブランチで質問できますが、入力の残りの文字 x はありますか? 適切なマルチセット表現がある場合、これは (基本的に) 一定時間のクエリである必要があります。
最初のサブワードを取得したら、残りのマルチセットを保持し、それを新しい入力として扱い、そのアナグラムの残り (存在する場合) を見つけることができます。
一般的な剰余マルチセットの検索を高速化するために、メモ化を使用してこの手順を拡張します。
これは非常に高速です - 各トライトラバーサルは実際のサブワードを与えることが保証されており、各トラバーサルはサブワードの長さに比例して時間がかかります (そして、サブワードは通常、コーディング標準によって非常に小さいです)。ただし、本当にもっと高速なものが必要な場合は、前処理にすべての n グラムを含めることができます。n グラムは、n 個の単語が連続する任意の文字列です。もちろん、W = #words の場合、インデックス サイズ O(W) から O(W^n) にジャンプします。辞書のサイズによっては、n = 2 が現実的かもしれません。
そして、これが私の斬新な解決策です。
Jon Bentley の著書 Programming Pearls には、単語のアナグラムの検索に関する問題が含まれています。ステートメント:
与えられた英単語の辞書から、アナグラムのすべてのセットを見つけます。たとえば、「pots」、「stop」、および「tops」はすべて、互いの文字を並べ替えることで形成できるため、すべて互いのアナグラムです。
少し考えた結果、解決策は、検索している単語の署名を取得し、それを辞書内のすべての単語と比較することであることに気づきました。単語のすべてのアナグラムは、同じ署名を持つ必要があります。しかし、これを達成する方法は？私のアイデアは、算術の基本定理を使用することでした。
算術の基本定理は、
すべての正の整数 (数字の 1 を除く) は、1 つ以上の素数の積としての再配置を除いて、正確に 1 つの方法で表すことができます。
つまり、最初の 26 個の素数の配列を使用するという考え方です。次に、単語の各文字について、対応する素数 A = 2、B = 3、C = 5、D = 7 … を取得し、入力単語の積を計算します。次に、辞書内の各単語に対してこれを行い、単語が入力単語と一致する場合、それを結果のリストに追加します。
パフォーマンスは多かれ少なかれ許容範囲です。479828 語の辞書の場合、すべてのアナグラムを取得するのに 160 ミリ秒かかります。これはおよそ 0.0003 ミリ秒/ワード、または 0.3 マイクロ秒/ワードです。アルゴリズムの複雑さは、O(mn) または ~O(m) のようです。ここで、m は辞書のサイズ、n は入力単語の長さです。
コードは次のとおりです。
package com.vvirlan;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Date;
import java.util.List;
import java.util.Scanner;
public class Words {
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 };
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
String word = "hello";
System.out.println("Please type a word:");
if (s.hasNext()) {
word = s.next();
}
Words w = new Words();
w.start(word);
}
private void start(String word) {
measureTime();
char[] letters = word.toUpperCase().toCharArray();
long searchProduct = calculateProduct(letters);
System.out.println(searchProduct);
try {
findByProduct(searchProduct);
} catch (Exception e) {
e.printStackTrace();
}
measureTime();
System.out.println(matchingWords);
System.out.println("Total time: " + time);
}
private List<String> matchingWords = new ArrayList<>();
private void findByProduct(long searchProduct) throws IOException {
File f = new File("/usr/share/dict/words");
FileReader fr = new FileReader(f);
BufferedReader br = new BufferedReader(fr);
String line = null;
while ((line = br.readLine()) != null) {
char[] letters = line.toUpperCase().toCharArray();
long p = calculateProduct(letters);
if (p == -1) {
continue;
}
if (p == searchProduct) {
matchingWords.add(line);
}
}
br.close();
}
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;
}
private long time = 0L;
private void measureTime() {
long t = new Date().getTime();
if (time == 0L) {
time = t;
} else {
time = t - time;
}
}
}
プログラムによるアナグラムに関する重要な研究の 1 つは、Ars Magna と呼ばれるツールを使用した Michael Morton (Mr. Machine Tool) によるものです。これは彼の作品に基づいた軽い記事です。
これは、Jason Cohen が提案した Java での実用的なソリューションであり、trie を使用したソリューションよりもいくらか優れたパフォーマンスを発揮します。主なポイントは次のとおりです。
以下は、アナグラム キーのセットを見つける主な再帰コードです。
// recursive function to find all the anagrams for charInventory characters
// starting with the word at dictionaryIndex in dictionary keyList
private Set<Set<String>> findAnagrams(int dictionaryIndex, char[] charInventory, List<String> keyList) {
// terminating condition if no words are found
if (dictionaryIndex >= keyList.size() || charInventory.length < minWordSize) {
return null;
}
String searchWord = keyList.get(dictionaryIndex);
char[] searchWordChars = searchWord.toCharArray();
// this is where you find the anagrams for whole word
if (AnagramSolverHelper.isEquivalent(searchWordChars, charInventory)) {
Set<Set<String>> anagramsSet = new HashSet<Set<String>>();
Set<String> anagramSet = new HashSet<String>();
anagramSet.add(searchWord);
anagramsSet.add(anagramSet);
return anagramsSet;
}
// this is where you find the anagrams with multiple words
if (AnagramSolverHelper.isSubset(searchWordChars, charInventory)) {
// update charInventory by removing the characters of the search
// word as it is subset of characters for the anagram search word
char[] newCharInventory = AnagramSolverHelper.setDifference(charInventory, searchWordChars);
if (newCharInventory.length >= minWordSize) {
Set<Set<String>> anagramsSet = new HashSet<Set<String>>();
for (int index = dictionaryIndex + 1; index < keyList.size(); index++) {
Set<Set<String>> searchWordAnagramsKeysSet = findAnagrams(index, newCharInventory, keyList);
if (searchWordAnagramsKeysSet != null) {
Set<Set<String>> mergedSets = mergeWordToSets(searchWord, searchWordAnagramsKeysSet);
anagramsSet.addAll(mergedSets);
}
}
return anagramsSet.isEmpty() ? null : anagramsSet;
}
}
// no anagrams found for current word
return null;
}
ここからレポをフォークして、それで遊ぶことができます。私が見逃したかもしれない多くの最適化があります。しかし、コードは機能し、すべてのアナグラムを見つけます。
数か月前に、アナグラムを計算する次の方法を使用しました。
辞書の各単語の「コード」を計算します。たとえば、['a', 2] で始まり ['z', 101] で終わる、アルファベットの文字から素数までのルックアップ テーブルを作成します。前処理ステップとして、ルックアップ テーブルで構成されている各文字の素数を検索し、それらを乗算することにより、辞書内の各単語のコードを計算します。後で検索するために、コードから単語へのマルチマップを作成します。
上で概説したように、入力単語のコードを計算します。
multimap 内の各コードの codeInDictionary % inputCode を計算します。結果が 0 の場合、アナグラムが見つかり、適切な単語を検索できます。これは、2 語以上のアナグラムでも機能します。
お役に立てば幸いです。
Jon Bentley による本Programming Pearlsは、この種のことを非常にうまくカバーしています。必読です。
私はそれをどのように見ていますか：
順序付けられていない文字のセットをリストの単語にマップするテーブルを作成する必要があります。つまり、辞書を調べて、次のようになります。
lettermap[set(a,e,d,f)] = { "deaf", "fade" }
次に、最初の単語から、一連の文字を見つけます。
astronomers => (a,e,m,n,o,o,r,r,s,s,t)
次に、そのセットのすべてのパーティションをループし (これは最も技術的な部分であり、考えられるすべてのパーティションを生成するだけです)、その文字セットの単語を検索します。
編集:うーん、これはほとんどジェイソン・コーエンが投稿したものです。
編集：さらに、質問へのコメントは、例のように「良い」アナグラムを生成することに言及しています:)。考えられるすべてのアナグラムのリストを作成したら、それらを WordNet で実行して、意味的に元のフレーズに近いものを見つけてください :)
すべての単語が一意であり、キーが単語のバイナリ (または 16 進数) 表現であるため、辞書をハッシュマップとして使用するとします。次に、単語があれば、O(1) の複雑さでその意味を簡単に見つけることができます。
ここで、すべての有効なアナグラムを生成する必要がある場合、生成されたアナグラムが辞書にあるかどうかを確認する必要があります。辞書に存在する場合は有効なアナグラムであり、そうでない場合は無視する必要があります。
最大100文字（またはそれ以上ですが制限があります）の単語が存在できると仮定します。
したがって、単語「hello」のようなインデックスのシーケンスとして取得する単語は、「1234」のように表すことができます。現在、「1234」のアナグラムは「1243」、「1242」などです。
必要な唯一のことは、特定の文字数のインデックスのすべての組み合わせを格納することです。これは 1 回限りのタスクです。そして、インデックスから文字を選択することにより、組み合わせから単語を生成できます。したがって、アナグラムを取得します。
アナグラムが有効かどうかを確認するには、辞書にインデックスを付けて検証します。
処理する必要があるのは重複だけです。これは簡単に行うことができます。辞書で検索された以前のものと比較する必要がある場合。
このソリューションは、パフォーマンスを重視します。
少し前に、2 つの単語のアナグラムをすばやく見つける方法についてのブログ記事を書きました。これは非常に高速に動作します。Ruby プログラムでは、300,000 語 (4 メガバイト) を超えるテキストファイルから単語の 44 個の 2 語アナグラムをすべて見つけるのに、わずか 0.6 秒しかかかりません。
文字でソートされた単語からこれらの文字を使用する単語のリストへの大きなハッシュ マッピングに単語リストを前処理できる場合、アプリケーションを高速化することができます。この前処理されたデータはシリアル化され、それ以降使用できます。
私の頭から離れて、最も理にかなっている解決策は、入力文字列からランダムに文字を選び、それで始まる単語に基づいて辞書をフィルタリングすることです。次に、別の文字を選択し、2番目の文字でフィルタリングします。さらに、残りのテキストで作成できない単語を除外します。次に、単語の終わりに到達したら、スペースを挿入して、残りの文字で最初からやり直します。単語の種類に基づいて単語を制限することもできます（たとえば、2つの動詞が隣り合っていない、2つの記事が隣り合っていないなど）。
この後、ある種の再帰的で徹底的な検索を行う必要があります。擬似コードは非常に大まかに次のとおりです。
function FindWords(solutionList, wordsSoFar, sortedQuery)
// base case
if sortedQuery is empty
solutionList.Add(wordsSoFar)
return
// recursive case
// InitialStrings("abc") is {"a","ab","abc"}
foreach initialStr in InitalStrings(sortedQuery)
// Remaining letters after initialStr
sortedQueryRec := sortedQuery.Substring(initialStr.Length)
words := words matching initialStr in the dictionary
// Note that sometimes words list will be empty
foreach word in words
// Append should return a new list, not change wordSoFar
wordsSoFarRec := Append(wordSoFar, word)
FindWords(solutionList, wordSoFarRec, sortedQueryRec)
最後に、solutionList を反復処理し、各サブリスト内の単語をスペースで区切って出力する必要があります。これらのケースでは、すべての順序を印刷する必要がある場合があります (たとえば、「I am Sam」と「Sam I am」はどちらもソリューションです)。
もちろん、私はこれをテストしていません。これは力ずくのアプローチです。