Iconミニ講座５（文字列分解・辞書参照）
今日は、当地では、午前中は日が差していましたが、午後に雲が広がって曇空に。
暑さ寒さに弱い私には、涼しくて好都合なのですが。
さて今回は、今までのまとめで、文字列を分解したもので辞書を参照する処理
をやります。 プログラムは、辞書参照の所で、文字列分解パターン（切り出す
文字列の長さ）を取り出してきて、それに従い順に部分文字列で辞書を参照します。
move()という関数出てきますが、これは文字列に対するポインターを動かすもの
です。
"abcde" ? write(move(2)) とすると、"abcde"を走査対象文字列として、
最初はポインターは先頭の "a"の手前にあります。
move(2)で、ポインターは２文字分進んで、"b"と"c"の中間に来ます。
move(2)の値は、その進んだ２文字分の間の文字列 すなわち "ab"と
なります。 write(move(2))で、"ab"の書き出しができます。
もう一度、write(move(2))とすると、"cd"が書き出せます。
このように、文字列から順に指定長の部分文字列を取り出すことができます。
-----^ DICREFPD.ICN ( date:03-08-21 time:19:10 ) -----------<cut here
####################
# 辞書読込・文字列順列生成／分割・辞書参照
####################
# dicrefpd.icn Rev.1.0 2003/08/21 windy 風つかい H.S.
####################
# Usage dicrefpd 英文字列 最大分割数 最小文字長
# english.dicは、スペルチェック用の英単語が順に並んだもの。
# このプログラムのテストでは、DD SOFT SoundMixSpellコンポーネント
# Ver 0.3.0 に 同梱の辞書ファイルを使用。
# 5文字の文字列を、5=2+2+1に分割した時に 2のところで、ダブリが生じる。
# 例えば、"ab"、"cd"、"e"が辞書にあれば ab cd e と cd ab eが出力される。
# This file is in the public domain.
procedure main(args)
# コマンドライン引数チェック。無ければ Usage表示
if *args < 1 then stop("dicrefpd 文字列 最大分割数 最小文字長")
# 辞書読込
dic := "english.dic" # 辞書ファイル名
dir := open(dic) | stop(dic," が見つかりません") # 辞書ファイルオープン
S_dic := set() # 辞書格納 set生成
# write(&errout,dic," を読込中です。") # 辞書読み込み
write(dic," を読込中です。") # 辞書読み込み
# write(&errout,"開始:",&clock)
write("開始:",&clock)
n_line := 0 # 辞書行数カウンタ
while word := read(dir) do { # 辞書を１行ずつ読み込んで、
insert(S_dic,word) # setに登録
n_line +:= 1
if n_line % 1000 = 0 then writes(&errout,"*") # 読み込み状況表示
}
close(dir) # 辞書ファイルクローズ
write(&errout)
# write(&errout,"終了:",&clock)
write("終了:",&clock)
# write(&errout,dic," の読込を終わりました。\n",*S_dic," 語ありました。")
write(dic," の読込を終わりました。\n",*S_dic," 語ありました。")
# コマンドラインの引数の順列を生成し、辞書を参照
c_word := args[1]
ndiv := \args[2] | 1 # 分割数指定無しは、１（分割せず）
nmin := \args[3] | *c_word # 最小文字長指定無しは、引数文字列長
n_comb := 0 # 組合せ数カウンタ
n_find := 0 # 辞書にある件数カウンタ
L_pat := [] # 文字列分割パターン格納 list
every put(L_pat,n_divdf(*c_word,ndiv,nmin)) # 分割パターン格納
# write(&errout,"\n",c_word," を、最大分割数 ",ndiv,"、最小文字長 ",nmin,
# " にて分割して、その全てが辞書にあるかチェック中。")
write("\n",c_word," を、最大分割数 ",ndiv,"、最小文字長 ",nmin,
" にて分割して、その全てが辞書にあるかチェック中。")
# write(&errout,"開始:",&clock)
write("開始:",&clock)
# ↓コマンドライン文字列の組合せを順次取り出し
every s := exsperm(c_word) do {
every L := !L_pat do { # 文字列を細分するデータを取り出して
ERR := &null # 辞書参照エラーフラッグリセット
ss := "" # 細分後の文字列格納エリア
s ? { # sを走査対象として、
every (length := !L ) & /ERR do { # 細分文字数を取り出して、
# ↑既に辞書参照エラーが発生していなければ、
n_comb +:= 1 # チェック回数カウンタ＋１
if n_comb % 1000 = 0 then writes(&errout,"*") # チェック状況表示
sss := move(length) # 細分文字列の取り出し
# 細分文字が辞書に存在するかチェック
if member(S_dic,sss) then ss ||:= (sss || " ") # データ足し込み
else ERR := "ERR" # 参照エラーフラッグセット
}
# 細分文字列が全て辞書にあれば、書き出し
if /ERR then { # エラーフラッグが立っていなければ
n_find +:= 1 # カウンタ＋１
write(s," -> ",ss) # 組合せ文字列出力
writes(&errout,"!") # 合致表示
}
}
}
}
write(&errout)
# write(&errout,"終了:",&clock)
write("終了:",&clock)
# write(&errout,n_comb," 通りの組合せのうち、",n_find," 通りが辞書にありました。")
write(n_comb," 通りの組合せのうち、",n_find," 通りが辞書にありました。")
end
####################
# 正整数分割 generator
####################
# 5=3+2 等に数字分割する。この procedureは n_divdを呼びフィルターを掛けている。
# 分割パターンが多すぎる時に、制限をかけるために使用。
# arg [1]: 分割する元の数
# [2]: 最大分割数
# [3]: 最小数
# value : list
procedure n_divdf(r,ndiv,nmin)
every L := n_divd(r) do { # r の分割結果を取り出し
if *L <= ndiv then { # 分割数チェック（listのサイズチェック）
if L[*L] >= nmin then suspend L # 最小数チェック（降順に入っているので
} # 末尾の要素をチェック）
}
end
####################
# 正整数分割 generator
####################
# 5=3+2 等に分割する。分割は降順のみ許す。（例 5=2+3は除外）
# arg [1]: 分割される元の数（再帰の場合は、前の処理の余り）
# [2]: 最大数 （5=2+2+1 の場合に、最初の 2の時 3が余るが、再帰して 3の
# 分割を始める時、3からではなく 2から始めるための細工。降順手当。）
# value : 分解結果の数。listに格納
# Usage : every L := n_divd(r) do ...
procedure n_divd(r,max)
/max := r # 指定無きは、分割される元の数そのもの
if r < 1 then fail # 念のため
if r = 1 then return [1] # 再帰終了
# r >= 2 の場合
if r > max then rs := max # 分割（取り去る）数の最大数の設定。
else rs := r # 分割される数か 最大数指定の 小さい方
every i := rs to 1 by -1 do { # 上記指定数〜１迄、順に−１しながら
rr := r -i # 新たな余り
if rr = 0 then suspend [i] # 余りが無ければ
# 余りがあれば、再帰処理
else if rr > i then suspend [i] ||| n_divd(rr,i) # 余りが大き過ぎる時
else suspend [i] ||| n_divd(rr)
}
end
# 以下は、Icon入門講座から引用
####################
# 英文字の組み合わせ（同一文字指定対応）
####################
# 名称変更 expermute -> exsperm
# arg [1]: s string
# value: string
# Usage: every ss := exsperm(s) do ...
# Icon入門講座２（１８）
procedure exsperm(s) # string permutations
if *s = 0 then return "" #
ss := csort(s) # 文字列をソートする。(strings.icn)
suspend ss[i := new_pos(ss)] || exsperm(ss[1:i] || ss[i+1:0])
# ↑同一文字はスキップする
end
####################
# ソートされた文字列 sの左はじから、順に文字位置を出力する generator。
####################
# 手前の文字と同一ならスキップする。
# arg [1]: s string
# value: integer
# Usage: every i := new_pos(s) do ...
procedure new_pos(s)
ss := "" # 手前の文字を記憶しておく変数
every i := 1 to *s do {
if ss ~== s[i] then { # 手前の文字と違っていたら
ss := s[i] # 手前文字を更新
suspend i # i を返す。
}
}
end
####################
# BIPL(Icon基本ライブラリー)の strings.icnに含まれる 文字のソート procedure
####################
procedure csort(s) #: lexically ordered characters
local c, s1 # ローカル変数宣言（無くても良い）
s1 := "" # 初期値クリア
every c := !cset(s) do # 引数を cset(文字集合)へ変換し順に取り出す。
every find(c, s) do # 取り出した文字で、引数文字列を検索し、
s1 ||:= c # 見つかる度に、文字を s1に足し込む。
return s1
end
# csetから !で要素を取り出す時には、アルファベット順に取り出せる。
-----$ DICREFPD.ICN ( lines:176 words:675 ) ----------------<cut here
dicrefpd sundown 2 3 >e723 としますと、結果はこうなります。
知らない単語が沢山でてきます。
-----^ E723 ( date:03-08-21 time:19:15 ) -------------------<cut here
english.dic を読込中です。
開始:19:15:50
終了:19:15:59
english.dic の読込を終わりました。
257650 語ありました。
sunburn を、最大分割数 2、最小文字長 3 にて分割して、その全てが辞書にあるかチェック中。
開始:19:15:59
bunsnur -> buns nur
bunsrun -> buns run
bunsurn -> buns urn
burnnus -> burn nus
burnsun -> burn sun
bursnun -> burs nun
nubsnur -> nubs nur
nubsrun -> nubs run
nubsurn -> nubs urn
nunsbur -> nuns bur
nunsrub -> nuns rub
nunsurb -> nuns urb
nursbun -> nurs bun
nursnub -> nurs nub
rubsnun -> rubs nun
runsbun -> runs bun
runsnub -> runs nub
snubnur -> snub nur
snubrun -> snub run
snuburn -> snub urn
sunburn -> sunburn
sunnbur -> sunn bur
sunnrub -> sunn rub
sunnurb -> sunn urb
urbsnun -> urbs nun
urnsbun -> urns bun
urnsnub -> urns nub
終了:19:15:59
2592 通りの組合せのうち、27 通りが辞書にありました。
-----$ E723 ( lines:37 words:125 ) -------------------------<cut here
dicrefpd midnight 2 3 >e823 としますと、結果はこうなります。
-----^ E823 ( date:03-08-21 time:19:16 ) -------------------<cut here
english.dic を読込中です。
開始:19:16:14
終了:19:16:22
english.dic の読込を終わりました。
257650 語ありました。
midnight を、最大分割数 2、最小文字長 3 にて分割して、その全てが辞書にあるかチェック中。
開始:19:16:23
dightmin -> dight min
dightnim -> dight nim
midnight -> midnight
mightdin -> might din
mightnid -> might nid
mindthig -> mind thig
nightdim -> night dim
nightmid -> night mid
thigmind -> thig mind
thingdim -> thing dim
thingmid -> thing mid
終了:19:16:26
60954 通りの組合せのうち、11 通りが辞書にありました。
-----$ E823 ( lines:21 words:61 ) --------------------------<cut here
８文字を４文字＋４文字に分けた場合に、同じ組合せが２度出てきます。
mindthig -> mind thig と thigmind -> thig mind のところです。
今回は、とりあえず見なかったことに。（汗）
dicrefpd heavyrain 2 4 >e923 としますと、結果はこうなります。
-----^ E923 ( date:03-08-21 time:19:17 ) -------------------<cut here
english.dic を読込中です。
開始:19:16:40
終了:19:16:48
english.dic の読込を終わりました。
257650 語ありました。
heavyrain を、最大分割数 2、最小文字長 3 にて分割して、その全てが辞書にあるかチェック中。
開始:19:16:48
aviaryhen -> aviary hen
hairynave -> hairy nave
hairyvane -> hairy vane
hairyvena -> hairy vena
havenairy -> haven airy
haverayin -> haver ayin
hayervain -> hayer vain
hayervina -> hayer vina
heavyairn -> heavy airn
heavyrain -> heavy rain
heavyrani -> heavy rani
hieranavy -> hiera navy
hyenariva -> hyena riva
hyenavair -> hyena vair
invaryeah -> invar yeah
naiverhay -> naiver hay
naiveryah -> naiver yah
navierhay -> navier hay
navieryah -> navier yah
nerviayah -> nervi ayah
rainyhave -> rainy have
ravenhiya -> raven hiya
ravinehay -> ravine hay
ravineyah -> ravine yah
ravinyeah -> ravin yeah
rayahnevi -> rayah nevi
rayahvein -> rayah vein
rayahvine -> rayah vine
rivenayah -> riven ayah
vahineray -> vahine ray
vahinerya -> vahine rya
vahineyar -> vahine yar
vainerhay -> vainer hay
vaineryah -> vainer yah
veinyhaar -> veiny haar
viharanye -> vihara nye
viharayen -> vihara yen
vinerayah -> viner ayah
vineryaah -> vinery aah
vineryaha -> vinery aha
終了:19:17:21
545145 通りの組合せのうち、40 通りが辞書にありました。
-----$ E923 ( lines:50 words:178 ) -------------------------<cut here
この場合、545145 通りで、３３秒かかっています。 これに１文字の曖昧検索が
できるようににすると、単純に作ると ２６倍かかるプログラムになりそうな気が
します。 ２文字の曖昧検索にすると、更にその２６倍？
曖昧検索を入れるのでしたら、検索方式を根本的に考え直した方が良さそうです。
heavyrainの例ですと、'a'が２個、'ehinrvy'の各文字が１個ずつの単語もしくは
単語の組合せが辞書にあるか？ という問題で、解法は色々あると思います。
９文字の文字列で５４万通りというと、辞書単語数２６万語を越えていますので、
これ以上の文字数を対象とするには、方式を考え直した方が良いだろうと思います。
今のプログラムの工夫でも速くなるとは思いますが。 あるいは、マシンを速い物
にしたりメモリー増設するという手もありますが、先立つものが．．．
しばらく、Iconを動かしていませんでしたが、くすのきさんに面白い題材を提供
して頂いたお陰で、多少 Iconのリハビリができました。ありがとうございます。
Iconは、この題材のような文字列をいじりまわす処理のために作られた言語です。
ご興味をお持ちになった方がいらっしゃれば、うれしいです。
風つかい(hshinoh@...)
IconのWWWは、 http://www.cs.arizona.edu/icon/
UniconのWWWは、http://unicon.sourceforge.net/index.html
BGM: Battery's not included ／ 森山威男＆杉本喜代志
番号順一覧Top
スレッド順一覧Top
518. Re: Iconミニ講座１（辞書読込） [Hiroshi Shinohara] 2003/8/21(19:27)
520. Re: Iconミニ講座１（辞書読込） [藤岡和夫] 2003/8/21(22:47)
512. Iconミニ講座（前説） [Hiroshi Shinohara] 2003/8/20(00:07)