Rubyでアナグラムしようよ

アナグラム(anagram)をご存知ですか？
アナグラムは単語や文の文字を入れ替えて
別の意味を持った単語や文を作る遊びです
例えば"note"には"tone"
"master"には"stream"というアナグラムがあります

もちろん日本語アナグラムもあります
"タモリ"は"モリタ"のアナグラムです
"いきるいみなんて"と"みんないきている"は
一見哲学的問答に見えますが
これもアナグラムなんです:)

少しやって頂ければ分かりますが
アナグラムを見つけるのは意外と難しいです
試しに"friend" と"setter"と"resort"のアナグラムを
それぞれちょっと考えてみてください
(答え)*1

そんなわけで..

Rubyにアナグラムを見つけてもらいましょう

RubyでAnagramを作る

指定の英単語に対する
複数のアナグラムを見つけるプログラムを考えます
こんな感じです

 find_anagrams('name') # => ['mean', 'amen']

これを実現するには少なくとも次のステップが必要そうです

1. 英単語リストを用意する
2. 指定単語のアナグラムを英単語リストから見つけ出す

指定単語のアナグラムを英単語リストから見つけ出す

単語リストはどこかにきっとあるでしょうから
後回しにして..
アナグラムを見つける方法を先に考えます

先に示した"name"と"mean"と"amen"はアナグラムですが
どうやってRubyにそれを判断させればいいでしょうか

いい方法を思いつきました
単語を文字で区切って配列化し引き算するんです

w1 = 'name'
w2 = 'mean'
w3 = 'amen'
w4 = 'man'
ws1 = w1.split(//) # => ["n", "a", "m", "e"]
ws2 = w2.split(//) # => ["m", "e", "a", "n"]
ws3 = w3.split(//) # => ["a", "m", "e", "n"]
ws4 = w4.split(//) # => ["m", "a", "n"]

ws1 - ws2 # => []
ws1 - ws3 # => []
ws1 - ws4 # => ["e"]

空配列になったらアナグラムです!

と言いたいのですがこれはダメです

w1 = 'name'
w5 = 'amenman'
w1.split(//) - w5.split(//) # => []

w1 = 'aaabbbccc'
w2 = 'abc'
w1.split(//) - w2.split(//) # => []

引く配列要素が多かったり
重複要素がある場合は
期待する結果になりません

実はいい方法があります
各単語のシグネチャーを作って
これを比較するのです
でこのシグネチャーは何かというと
単語の文字をソートしたものです

w1 = 'name'
w1.chars.sort.join.intern # => :aemn

アナグラムな単語は
このシグネチャーがおなじになるはずです

やってみましょう

w1 = 'name'
w2 = 'mean'
w3 = 'amen'
w4 = 'amenman'
sig1 = w1.chars.sort.join.intern # => :aemn
sig2 = w2.chars.sort.join.intern # => :aemn
sig3 = w3.chars.sort.join.intern # => :aemn
sig4 = w4.chars.sort.join.intern # => :aaemmnn
sig1 == sig2 # => true
sig1 == sig3 # => true
sig1 == sig4 # => false

いいですね!*2

ではこれをメソッド化しておきましょう

def signature(word)
  word.downcase.chars.sort.join.intern
end

%w(name mean amen man).map { |word| signature word } # => [:aemn, :aemn, :aemn, :amn]

単語リスト

さて次に単語リストを用意します
ネットから拾う手もありますが
都合の良いことにMacの /usr/share/dict/
には最初から単語リストwordsが入ってるんです

覗いてみます

% head /usr/share/dict/words
A
a
aa
aal
aalii
aam
Aani
aardvark
aardwolf
Aaron

% tail /usr/share/dict/words 
zymotoxic
zymurgy
Zyrenian
Zyrian
Zyryan
zythem
Zythia
zythum
Zyzomys
Zyzzogeton

語数を調べましょう

% wc -l /usr/share/dict/words
  234936 /usr/share/dict/words

十分ですね

アナグラム辞書

さて先の方針で
単語同士を直接比較するのではなくて
そのシグネチャーを比較することとしました
ですから単語リストの各単語をそのシグネチャーで
引ける辞書(アナグラム辞書)を作る必要があります
毎回単語リストのシグネチャーを計算するのは
効率的ではありませんからね

データ構造は次のようなものがよさそうです

{:aemn => ['name', 'mean', 'amen'], :amn => ['man']}

シグネチャーをkeyとして
それを持った単語のリストをvalueとするハッシュです

それでは単語リストからアナグラム辞書を作る
build_anagramsメソッドを定義しましょう
入力は単語の配列です

def build_anagrams(words)
  words.map { |word| [signature(word), word] }
       .inject({}) { |h, (sign, word)| h[sign] ||= []; h[sign] << word; h }
       .select { |sign, words| words.size > 1 }
end

まずmapでシグネチャーと単語の組みを作って
injectで共通のシグネチャーの指す配列に単語を追加していきます
injectの使い方では注意点が２つあります
１つは h[sign] ||= [] での初期化が必要なこと
１つは各イテレートでハッシュhを返すことです
ちなみに次のような書き方もできます

def build_anagrams(words)
  mem = Hash.new{|h, k| h[k] = []}
  words.map { |word| [signature(word), word] }
       .each_with_object(mem) { |(sign, word), h| h[sign] << word }
       .select { |sign, words| words.size > 1 }
end

さてこのメソッドを試してみましょう

word_list = %w(name mean amen man)
Anagrams = build_anagrams(word_list) # => {:aemn=>["name", "mean", "amen"], :amn=>["man"]}

いいですね!

これでもう最初に示した
find_anagramsメソッドが書けますね

def find_anagrams(word)
  sign = signature(word)
  res = Anagrams[sign]
  res ? res - [word] : []
end

find_anagrams("name") # => ["mean", "amen"]
find_anagrams("age") # => []

単語リストの読み込み

ここまで来ればあと一歩です
単語リストのファイルをオープンして
メモリー上に読み出し
そこから単語の配列を作ります
最初は小さな単語ファイル(sample)を用意して
試してみるのがいいですね

name
mean
amen
man
man
MAN
street
sweet
Tester
retest
word
world

tower
rowet
WROTE
X
a
monopersulphuric
b

コードは次のようになります

def build_wordlist(path)
  File.open(path) do |f|
    f.map { |line| line.chomp.downcase }.uniq.reject { |word| word.size < 2 }
  end
end

WORDS = build_wordlist('./sample') # => ["name", "mean", "amen", "man", "street", "sweet", "tester", "retest", "word", "world", "tower", "rowet", "wrote", "monopersulphuric"]

改行を除去して全て小文字化し
重複と空行と一文字単語を除去します

さあ完成です!
コードをまとめてみましょう

Rubyならアナグラムも簡単ですね!

Anagramライブラリ

で　ここまでやったので
Anagramライブラリを書いて見ました
Rspecの練習を兼ねまして..^^;

melborne/anagram - GitHub

anagramコマンド

後述するAnagram辞書を作ると
Terminalでanagramコマンドが使えます

% ./anagram dream team ruby
dream => ["armed", "derma", "ramed"]
team => ["mate", "meat", "meta", "tame", "tema"]
ruby => ["bury"]

アナグラムを見つけたい１または複数の単語を
コマンドの引数として渡します

Anagram辞書の作成

Anagram.buildクラスメソッドで
Anagram辞書を作ります

% irb
>> require 'anagram'
>> 
>> File.open('/usr/share/dict/words') do |f|
>>   Angram.build(f)
>> end

辞書はカレントディレクトリに
YAMLファイル(anagram.yml)で保存されます

Anagram.findクラスメソッド

Anagram辞書ができれば
findクラスメソッドが使えます

>> Anagram.find 'time' #=> ["emit", "item", "mite"]
>> Anagram.find 'beer' #=> ["bere", "bree"]

Anagram.anagrams?クラスメソッド

このメソッドは引数に渡した単語同士が
アナグラムか検査します

>> Anagram.anagrams? 'beer', 'bair' #=> false
>> Anagram.anagrams? 'time', 'emit', 'item' #=> true

anagrams?メソッドは日本語でも文章でも使えます

>> Anagram.anagrams? 'いきるいみなんて', 'みんないきている' #=> true
>> sentence1 = "To be or not to be: that is the question; whether 'tis nobler in the mind to suffer the slings and arrows of outrageous fortune..."
>> sentence2 = "In one of the Bard's best-thought-of tragedies our insistent hero, Hamlet, queries on two fronts about how life turns rotten."
>> Anagram.anagrams?(sentence1, sentence2) #=> true

こんな長いアナグラムを考える人がいるんですね..

Anagramオブジェクト

Anagram.newでAnagramオブジェクトを生成することで
Anagram#find #longest #most および#all
の各メソッドが使えるようになります
Anagram#findはAnagram.findと同じです

>> an = Anagram.new
>> an.find 'visit' #=> ["vitis"]
>> an.find 'master' #=> ["martes", "remast", "stream"]
>> an.find 'version' #=> []
>> an.find 'bridge' #=> ["begird"]
>> an.find 'paper' #=> ["rappe"]
>> an.find 'speech' #=> []
>> an.find 'take' #=> ["kate", "keta", "teak"]
>> an.find 'language' #=> ["ganguela"]
>> 

Anagram#longest は辞書における
長い単語のアナグラムを上位から表示します
Anagram#most は最も組数の多い
アナグラムを上位から表示します

>> an.longest(size:10).each {|l| p l}
["hydropneumopericardium", "pneumohydropericardium"]
["cholecystoduodenostomy", "duodenocholecystostomy"]
["glossolabiopharyngeal", "labioglossopharyngeal"]
["chromophotolithograph", "photochromolithograph"]
["duodenopancreatectomy", "pancreatoduodenectomy"]
["anatomicopathological", "pathologicoanatomical"]
["encephalomeningocele", "meningoencephalocele"]
["glossolabiolaryngeal", "labioglossolaryngeal"]
["anatomicophysiologic", "physiologicoanatomic"]
["pericardiacophrenic", "phrenicopericardiac"]

>> an.most(size:10).each {|m| p m}
["angor", "argon", "goran", "grano", "groan", "nagor", "orang", "organ", "rogan", "ronga"]
["elaps", "lapse", "lepas", "pales", "salep", "saple", "sepal", "slape", "spale", "speal"]
["caret", "carte", "cater", "crate", "creat", "creta", "react", "recta", "trace"]
["ester", "estre", "reest", "reset", "steer", "stere", "stree", "terse", "tsere"]
["leapt", "palet", "patel", "pelta", "petal", "plate", "pleat", "tepal"]
["armet", "mater", "metra", "ramet", "tamer", "terma", "trame", "trema"]
["asteer", "easter", "eastre", "reseat", "saeter", "seater", "staree", "teaser"]
["arist", "astir", "sitar", "stair", "stria", "tarsi", "tisar", "trias"]
["laster", "lastre", "rastle", "relast", "resalt", "salter", "slater", "stelar"]
["dater", "derat", "detar", "drate", "rated", "trade", "tread"]

Anagram#all は辞書における
すべてのアナグラムの組みを表示します

>> an.all.size #=> 14212
>> an.all.take 5 #=> [["aal", "ala"], ["aam", "ama"], ["aaronic", "nicarao", "ocarina"], ["aaronite", "aeration"], ["aaru", "aura"]]
>> an.all.select {|set| set.size > 3 && set.first =~ /^ru/}
=> [["ruinate", "taurine", "uranite", "urinate"], ["runite", "triune", "uniter", "untire"], ["rusa", "saur", "sura", "ursa", "usar"], ["ruse", "suer", "sure", "user"]]

なおAnagram.newは単語リストファイルを
引数に取ることができます

>> an = Anagram.new(open 'sample_dic')

こうするとAnagram辞書を作らずに
各インスタンスメソッドが使えるようになります

暇なときに遊んでやってください :-)

(追記:2011-12-07) コードを一部修正しました。

*1:"friend"には["finder", "redfin", "refind"], "setter"には["retest" "street" "tester"], "resort"には["roster", "sorter", "storer"]があります

*2:この方法は「珠玉のプログラミング」に載っていました。