![[PukiWiki]](skin/modernskin/logo.png "[PukiWiki]"){kind=logo}
[[TSNETWiki]] Icon入門講座６ Iconミニ講座 2003/9/26 風つかい --- TS Network への書込から --- (hshinoh@mb.neweb.ne.jp) ■ TSfree > Iconミニ講座（前説） 風つかい 残梅雨お見舞い申し上げます。残暑じゃなくて、梅雨が未だ残っているような 天気ですね。 火星大接近とかいうニュースで夜空を見上げても、雲ばかり。 さて、先日、TS Networkの TSabcで、クロスワードパズルの関係で、面白い題材を 提供して頂いています。 こんなケースです。 ・英文字のクロスワードパズルをまず解いて、その後指定の升目の文字を 組み合わせて最終的な単語を見つける。 ・しかし、一部判っていない升目がある。 ・辞書は、英語の単語がズラッと並んだ形式の辞書ファイルがある。 ・サンプル 判らない文字を .で表すと、a.ahviy.r となる。 尚、この場合の正解は、heavy rain という２つの単語の組合せだそう です。 というこことがありまして、Icon版で簡単な支援プログラムを作ってみたのですが お盆休みに、もう少し機能アップできないかと考えてみました。 少し整理して、アップしてみます。 ・指定文字の順列組合せの生成 （これは、比較的簡単。TSabcにアップ済み。） ・その順列を分けて、単語候補を生成 heavyrain -> heavy rainと分ける ・辞書の検索（不明文字があるので、曖昧検索が必要） あたりを考えてみたのですが、 ・曖昧検索は、一挙に処理時間が増えてしまいそうなので、パス。 heavyではなく、h.avyだと、"."は a-zの可能性があるので、一挙に 26倍に なってしまいます。 ・文字列を分割して、単語候補を生成する。これはできそう。 これには、まず、5文字の文字列だと、 5文字の単語、4+1文字、3+2文字、3+1+1文字、2+2+1文字、2+1+1+1文字、 1+1+1+1+1文字等の組合せが考えられます。 あまりに多い分割数とか、短い単語はある程度無視して良いかと思います。 ・英語辞書は、スペルチェック用のフリーの辞書を探す。 辞書は、最初に一挙に読み込んで、setに登録し、それを使って検索する。 こんなところで、やってみましょう。 Iconのプログラムおよびライブラリーは、次の所から 入手できます。 http://www.cs.arizona.edu/icon/ この講座は、TS Networkの TSfree メーリングリストにポストしたものに加筆・修正 を行ったものです。 Iconは PDSですので、この講座も同じ扱いとします。（転載・編集自由） (This textbook is in the public domain.) Iconミニ講座 目次 内容 第１回 辞書読込 ファイル読込、set(集合)生成・格納・参照 第２回 組合せ文字列の辞書参照 順列生成(nPm)、set参照 第３回 正整数の分割 生成数の部分和、再帰プログラム 第４回 フィルター generatorとフィルター 第５回 文字列分解・辞書参照 文字列の分解・繰り返し参照 第６回 辞書参照の別方式 table生成・格納・参照 第７回 曖昧参照 組合せ生成(nHm) 第８回 辞書分割 ファイル書込み 第９回 分配組合せ 文字列の組合せ分配 第１０回 分割文字で辞書参照 繰り返し参照 おまけ プログラムの整理 link あまり procedure構成 再帰・every・while 風つかい(hshinoh@mb.neweb.ne.jp) IconのWWWは、 http://www.cs.arizona.edu/icon/ UniconのWWWは、http://unicon.sourceforge.net/index.html BGM: Battery's not included ／森山威男＆杉本喜代志 (2003/08/20 TSfree0.txt) ■ TSfree > Iconミニ講座１（辞書読込） 風つかい 今回は、辞書の読み込みです。 辞書と言っても、単語がずらっと並んでいる テキストファイルですので、テキストファイルの読込プログラムと変わりはあり ません。 後々、時間が問題に気になりそうなので、現在時刻を書き出すように しました。 &clockは、現在時刻を hh:mm:ss形式で保持している組込キーワード です。 最初、動作モニター用の表示は、エラー出力へ出していましたが、 アップの都合上、標準出力へ出すように修正してあります。 -----^ DICREF.ICN ( date:03-08-19 time:23:32 ) -------------<cut here #################### # 辞書読込・辞書参照の習作。 #################### # dicref.icn Rev.1.0 2003/08/19 windy 風つかい H.S. #################### # Usage dicref 文字列 # english.dicは、スペルチェック用の英単語が順に並んだもの。 # このプログラムのテストでは、DD SOFT SoundMixSpellコンポーネント # Ver 0.3.0 に 同梱の辞書ファイルを使用。 # This file is in the public domain. procedure main() # 辞書読込 dic := "english.dic" # 辞書ファイル名 dir := open(dic) | stop(dic," が見つかりません") # 辞書ファイルオープン S_dic := set() # 辞書格納 set生成 # write(&errout,dic," を読込中です。") # 辞書読み込み write(dic," を読込中です。") # 辞書読み込み # write(&errout,"開始:",&clock) write("開始:",&clock) n := 0 # 辞書行数カウンタ while word := read(dir) do { # 辞書を１行ずつ読み込んで、 insert(S_dic,word) # setに登録 n +:= 1 if n % 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," 語ありました。") # 辞書参照テスト L := ["heavy","rain","yveah","niar"] # テストデータ # write(&errout,"参照テストを開始します。") write("参照テストを開始します。") # write(&errout,"開始:",&clock) write("開始:",&clock) every s := !L do { # テストデータを順次読み出し writes(s) if member(S_dic,s) then write(": OK") # 辞書にあるかチェック else write(": NG") } # write(&errout,"終了:",&clock) write("終了:",&clock) # write(&errout,"参照テストを終わりました。") write("参照テストを終わりました。") end -----$ DICREF.ICN ( lines:53 words:154 ) -------------------<cut here dicref >aaa としますと、こんな結果になります。 -----^ AAA ( date:03-08-19 time:23:35 ) --------------------<cut here english.dic を読込中です。 開始:23:35:43 終了:23:35:51 english.dic の読込を終わりました。 257650 語ありました。 参照テストを開始します。 開始:23:35:51 heavy: OK rain: OK yveah: NG niar: NG 終了:23:35:51 参照テストを終わりました。 -----$ AAA ( lines:13 words:20 ) ---------------------------<cut here 私のＰＣでは、辞書読込・setへの格納に、８秒ほどかかっています。 ＣＰＵ Celeronで、クロック ７３３Ｍ、メモリーは多分３２Ｍ、MS-DOS版 の Iconを、Windows-MEのＤＯＳ窓で動作させています。 風つかい(hshinoh@mb.neweb.ne.jp) IconのWWWは、 http://www.cs.arizona.edu/icon/ UniconのWWWは、http://unicon.sourceforge.net/index.html BGM: Battery's not included ／森山威男＆杉本喜代志 (2003/08/20 TSfree1.txt) ■ TSfree > Iconミニ講座２（組合せ文字列の辞書参照） 風つかい 今回は、 ・コマンドラインから入力した文字列の順列組合わせを作成 ・その組合せ文字が辞書にあるか参照し、あれば出力する 処理を行います。 前回の辞書読込の辞書参照の部分に、コマンドライン入力の文字列の順列組み 合わせを適用する構成となっています。 -----^ DICREFP.ICN ( date:03-08-20 time:18:18 ) ------------<cut here #################### # 辞書読込・文字列順列の辞書参照 #################### # dicrefp.icn Rev.1.0 2003/08/20 windy 風つかい H.S. #################### # Usage dicrefp 文字列 # english.dicは、スペルチェック用の英単語が順に並んだもの。 # このプログラムのテストでは、DD SOFT SoundMixSpellコンポーネント # Ver 0.3.0 に 同梱の辞書ファイルを使用。 # This file is in the public domain. procedure main(args) # コマンドライン引数チェック。無ければ Usage表示 if *args < 1 then stop("dicrefp 英単語") # 辞書読込 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] # write(&errout,c_word," の組合せが辞書にあるかチェック中です。") write(c_word," の組合せが辞書にあるかチェック中です。") # write(&errout,"開始:",&clock) write("開始:",&clock) n_comb := 0 # 組合せ数カウンタ n_find := 0 # 辞書にある件数カウンタ every word := exsperm(c_word) do { # 順列 generatorから文字を取り出し n_comb +:= 1 # カウンタ＋１ if n_comb % 1000 = 0 then writes(&errout,"*") # チェック状況表示 if member(S_dic,word) then { # 組合せ文字列が辞書にあれば、 n_find +:= 1 # カウンタ＋１ writes(&errout,"!") # 発見表示 write(word) # 組合せ文字列出力 } } write(&errout) # write(&errout,"終了:",&clock) write("終了:",&clock) # write(&errout,n_comb," 通りの組合せのうち、",n_find," 通りが辞書にありました。") write(n_comb," 通りの組合せのうち、",n_find," 通りが辞書にありました。") 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から !で要素を取り出す時には、アルファベット順に取り出せる。 -----$ DICREFP.ICN ( lines:110 words:369 ) -----------------<cut here dicrefp sunrise >bbb としますと、こんな結果になります。 -----^ BBB ( date:03-08-20 time:19:18 ) --------------------<cut here english.dic を読込中です。 開始:19:18:22 終了:19:18:30 english.dic の読込を終わりました。 257650 語ありました。 sunrise の組合せが辞書にあるかチェック中です。 開始:19:18:30 insures sunrise 終了:19:18:30 2520 通りの組合せのうち、2 通りが辞書にありました。 -----$ BBB ( lines:11 words:17 ) ---------------------------<cut here いくつかの単語で試してみましたが、短い単語ですと並べ替えで結構他の単語に なりますが、長い単語だと並べ替えてもうまくは他の単語にはならないみたいです。 風つかい(hshinoh@mb.neweb.ne.jp) IconのWWWは、 http://www.cs.arizona.edu/icon/ UniconのWWWは、http://unicon.sourceforge.net/index.html BGM: ふたりのビッグショー ～Talk百歌～ vol.7 ／篠原美也子＆奥井亜紀 (2003/08/20 TSfree2.txt) ■ TSfree > Iconミニ講座３（正整数の分割） 風つかい 今回は、正整数の部分和への分解です。これは、５文字の文字列があるとして、 例えば、３文字と２文字の２つの単語として、辞書を参照するためのものです。 ５の分解でも、５（分解しない）、４＋１、３＋２、３＋１＋１、．．．と いって、最後は１＋１＋１＋１＋１と、かなりのパターンが発生します。 こういう面倒な繰り返しが必要な処理は、再帰処理を行うとプログラムが楽に なることが多いみたいですね。 処理は、５の例ですと、５から順次 ５、４、３、２、１と引き算していく やり方にしています。 最初は、５から５を引くケースで、 余りは０です。 結果は［５］を返します。 次は、５から４を引くケースで、 余りは１です。余りがある場合は、中間結果として［４］を保持して、 自分自身を更に呼んで（再帰）、余りの１を与えて、結果をもらいます。 その結果として［１］が返って来ます。中間結果の［４］に［１］を追加して ［４，１］を結果として返します。 次は、５から３を引くケースで、 １回目の動作 中間結果１ ［３］ 余り ２ ・・・余り処理のため再帰 ２回目の動作 中間結果１ ［２］ 余り ０ ２ ［１］ 余り １ ・・・余り処理のため再帰 ３回目の動作 結果１ ［１］ という動作を経ますので、結果は［３，２］と、［３，１，１］の２つが返り ます。 こんな風な動作となります。 -----^ N_DIV.ICN ( date:03-08-20 time:19:43 ) --------------<cut here #################### # 正数分割 #################### # n_div.icn Rev.1.0 2003/08/20 windy 風つかい H.S. #################### # Usage n_div 正数 # 与えられた数字を部分和に分解する。 # 例:5->[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1] # This file is in the public domain. procedure main(args) Usage := "n_div 正数" if *args < 1 then stop(Usage) # コマンドライン引数が無ければ Usage表示 if args[1] < 1 then stop(Usage) # 正数でなければ Usage表示 # ↓正数分割 generatorから順次結果を取り出し every L := n_div(args[1]) do show_sl(L) # ↑listの内容を表示する end #################### # 正数分割 generator #################### # arg [1]: 分割される数（正数）（再帰の場合は、余り） # value : 分解結果の数 listに格納 # Usage : every L := n_div(r) do ... procedure n_div(r) if r < 1 then fail # 念のため if r = 1 then return [1] # 再帰終了 # r >= 2 の場合 every i := r to 1 by -1 do { # r から順に －１しながら rr := r -i # 元の数から引き算していく if rr = 0 then suspend [i] # 余りが ０なら結果を返す。 else suspend [i] ||| n_div(rr) # ↑余りがでたら、再帰してその結果を listの末尾 # に追加。 ||| は listの要素の追加演算子 } # suspend は、複数の結果を返す return end # 以下は、Icon入門講座より #################### # listの 内容表示 #################### # arg : list # value : null # Usage : show_sl(L) # 最終的に stringか numberが要素であること # Icon入門講座（１３）,Icon入門講座３（１５） procedure show_sl(list) # listの内容表示（test／表示用） every writes(" ",!list) write() return end -----$ N_DIV.ICN ( lines:57 words:192 ) --------------------<cut here n_div 5 >ccc としますと、こんな結果になります。 -----^ CCC ( date:03-08-20 time:19:44 ) --------------------<cut here 5 4 1 3 2 3 1 1 2 3 2 2 1 2 1 2 2 1 1 1 1 4 1 3 1 1 2 2 1 2 1 1 1 1 3 1 1 2 1 1 1 1 2 1 1 1 1 1 -----$ CCC ( lines:16 words:48 ) ---------------------------<cut here 以上の結果を良く見ますと、５＝４＋１と１＋４や ３＋２と２＋３の両方が 現れています。 辞書検索は、どちらか一方を行えば、残りは入れ替えるだけで 人が判断できると思います。 ということで、片方だけにするために、結果は、 降順しか許さないという条件を付けましょう。 ということで、再帰の際に制限 を付けました。 -----^ N_DIVD.ICN ( date:03-08-20 time:19:42 ) -------------<cut here #################### # 正数分割 #################### # n_divd.icn Rev.1.0 2003/08/20 windy 風つかい H.S. #################### # Usage n_divd 正数 # 与えられた数字を部分和に分解する。結果は降順の分解のみ。 # 例:5->[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1] # This file is in the public domain. procedure main(args) Usage := "n_divd 正数" if *args < 1 then stop(Usage) # コマンドライン引数が無ければ Usage表示 if args[1] < 1 then stop(Usage) # 正数でなければ Usage表示 # ↓正数分割 generatorから順次結果を取り出し every L := n_divd(args[1]) do show_sl(L) # ↑listの内容を表示する 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入門講座より #################### # listの 内容表示 #################### # arg : list # value : null # Usage : show_sl(L) # 最終的に stringか numberが要素であること # Icon入門講座（１３）,Icon入門講座３（１５） procedure show_sl(list) # listの内容表示（test／表示用） every writes(" ",!list) write() return end -----$ N_DIVD.ICN ( lines:63 words:231 ) -------------------<cut here n_divd 5 >ddd とすると結果は、こうなります。 だいぶパターンが減り ました。 それでも、未だ随分ありますので、分割数や最小数に制限をつけたい と思います。それは、次回に。 -----^ DDD ( date:03-08-20 time:19:45 ) --------------------<cut here 5 4 1 3 2 3 1 1 2 2 1 2 1 1 1 1 1 1 1 1 -----$ DDD ( lines:7 words:20 ) ----------------------------<cut here 風つかい(hshinoh@mb.neweb.ne.jp) IconのWWWは、 http://www.cs.arizona.edu/icon/ UniconのWWWは、http://unicon.sourceforge.net/index.html BGM: Battery's not included ／ 森山威男＆杉本喜代志 (2003/08/20 TSfree3.txt) ■ TSfree > Iconミニ講座４（フィルター） 風つかい 今回は、正整数の部分和への分解で、結構な数のパターンが生成されますので、 これに制限を掛けます。 分割数の制限と最小数の制限を付けられるようにします。 前回の n_divd.icn に制限を付ける処理を追加しても良いのですが、降順のみの 制限を付けるだけで結構面倒したので、更に修正する気は起きません。 そこで、n_divd.icnはそのままにして、n_divdを呼ぶ方で制限を付けようと思い ます。 あるプログラムの処理結果を、別のプログラムが加工して、更に別のプログラムに 渡すことを、フィルターと言いますので、この procedureも、フィルターと言って 良いと思います。 こんな格好の構成です。 +----------------+ +--------------+ +--------------+ | n_divd | | n_divdf | | main | | 正整数分割生成 | ---> | 分割数制限 | ---> | 結果を使用 | | | | 最小数制限 | | | | | | フィルター | | | | generator | | generator | | | +----------------+ +--------------+ +--------------+ -----^ N_DIVDF.ICN ( date:03-08-20 time:23:48 ) ------------<cut here #################### # 正整数分割 分割数・最小数制限付き #################### # n_divdf.icn Rev.1.0 2003/08/20 windy 風つかい H.S. #################### # Usage n_divdf 正整数 最大分割数 最小数 # 与えられた数字を部分和に分解する。結果は降順の分解のみ。 # 例:5->[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1] # この中で、最大分割数、最小数の制限に合うものを出力する。 # This file is in the public domain. procedure main(args) Usage := "n_divd 正整数 最大分割数 最小数" if *args < 1 then stop(Usage) # コマンドライン引数が無ければ Usage表示 if args[1] < 1 then stop(Usage) # 正数でなければ Usage表示 n := args[1] # ↓defaultはなるべく生成パターンが少なくなるよう ndiv := \args[2] | 1 # defaultの最大分割数は、１（分割せず） nmin := \args[3] | *n # defaultの最小数は、分割される数そのもの write(n," を、最大分割数 ",ndiv,"、最小数 ",nmin," にて分割") # ↓正整数分割 generatorから順次結果を取り出し every L := n_divdf(n,ndiv,nmin) do show_sl(L) # ↑listの内容を表示する 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入門講座より #################### # listの 内容表示 #################### # arg : list # value : null # Usage : show_sl(L) # 最終的に stringか numberが要素であること # Icon入門講座（１３）,Icon入門講座３（１５） procedure show_sl(list) # listの内容表示（test／表示用） every writes(" ",!list) write() return end -----$ N_DIVDF.ICN ( lines:86 words:320 ) ------------------<cut here n_divdf 9 3 3 >eee とすると、結果はこうなります。 相当、制限が付けられ ますね。 -----^ EEE ( date:03-08-21 time:00:00 ) --------------------<cut here 9 を、最大分割数 3、最小数 3 にて分割 9 6 3 5 4 3 3 3 -----$ EEE ( lines:5 words:13 ) ----------------------------<cut here さて、次回は、まとめです。 風つかい(hshinoh@mb.neweb.ne.jp) IconのWWWは、 http://www.cs.arizona.edu/icon/ UniconのWWWは、http://unicon.sourceforge.net/index.html BGM: Battery's not included ／ 森山威男＆杉本喜代志 (2003/08/21 TSfree4.txt) ■ TSfree > 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 sunburn 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@mb.neweb.ne.jp) IconのWWWは、 http://www.cs.arizona.edu/icon/ UniconのWWWは、http://unicon.sourceforge.net/index.html BGM: Battery's not included ／ 森山威男＆杉本喜代志 (2003/08/21 TSfree5.txt) ■ TSfree > Iconミニ講座６（辞書参照の別方式） 風つかい 前回で、ミニ講座は終わったつもりでいたのですが、辞書参照がどうもスッキリ しませんので、ツラツラ考えていました。（シツコイ！） 特定文字を使った単語をスバヤク検索するのだったら、 ・スバヤイ検索には、setか tableを使うのが良い。 ・同一文字を使った文字列に、何か共通のインデックスを付けて、テーブルに 登録しておけば、スバヤク検索できる。 ということで、 ・辞書の単語の文字列をソートしたもので、インデックスを作っておいて、 同一文字を使用した単語をまとめて、テーブルに登録しておき、 ・検索したい文字列をソートしたもので、テーブルを参照すれば、 ・一回の参照で、候補の単語群が見つかる。 と、気が付きました。 例えば、"abcd"と "cdab"と "dcab"という単語があったとして、皆ソートすると、 "abcd"となります。 ソートした "abcd"を インデックス（Iconでは keyと言い ます。）として、値に list形式で、["abcd","cdab","dcab"]と格納しておけば、 "abcd"で参照すれば、文字の配列を入れ替えた場合の候補が、一挙に出てきます。 この方式ですと、不明文字を、１～２文字入れて 26倍とか、26^2倍程度に処理が 増えても、ガマンできる時間で処理ができそうです。 ↓ソート 辞書 "abcd" ----> テーブル "cdab" ----> key: "abcd" ->value: ["abcd","cdab","dcab"] "dcab" ----> ↑ ｜参照 検索文字 --->ソート--------- という考えで、辞書読込・参照のプログラムを修正してみました。 辞書の登録文字にダブリがあります。setに登録する場合は問題は起きないのですが テーブルに登録する時に valueでダブルといけないので、チェックを入れてあります。 また keyは、小文字に統一して処理するようにしました。 -----^ DICREF2.ICN ( date:03-08-23 time:11:12 ) ------------<cut here #################### # 辞書読込・使用文字種毎の分類をした辞書参照の習作。 #################### # dicref2.icn Rev.1.0 2003/08/23 windy 風つかい H.S. #################### # Usage dicref2 # english.dicは、スペルチェック用の英単語が順に並んだもの。 # このプログラムのテストでは、DD SOFT SoundMixSpellコンポーネント # Ver 0.3.0 に 同梱の辞書ファイルを使用。 # This file is in the public domain. procedure main() # 辞書読込 dic := "english.dic" # 辞書ファイル名 dir := open(dic) | stop(dic," が見つかりません") # 辞書ファイルオープン S_dic := set() # 辞書ダブリチェック用 set生成 T_dic := table() # 辞書格納 table生成 write(dic," を読込中です。") # 辞書読み込み write("開始:",&clock) n := 0 # 辞書行数カウンタ while word := read(dir) do { # 辞書を１行ずつ読み込んで、 n +:= 1 if n % 1000 = 0 then writes(&errout,"*") # 読み込み状況表示 if member(S_dic,word) then writes(&errout,"?") # 登録済みならエラー表示 else { insert(S_dic,word) # setに登録 # 単語を小文字変換しソートしたものをインデックスにして格納 # 同一文字を含む単語は同じインデックスに listの要素として格納される。 # ↓文字列ソート s_word := csort(map(word)) # 小文字へ変換し、ソートして # ↑小文字変換 if member(T_dic,s_word) # 辞書テーブルにあるかチェック then put(T_dic[s_word], word) # あれば、その listに追加 else T_dic[s_word] := [word] # 無ければ、listに入れて登録 } } close(dir) # 辞書ファイルクローズ write(&errout) write("終了:",&clock) write(dic," の読込を終わりました。 ",*S_dic," 語ありました。") write("同一文字で構\成される単語をまとめると、",*T_dic," 種類となります。") # ↑Shift-JISでは、0x5cを含むので、"\"を補完。 # 辞書参照テスト L := ["heavy","rain","yveah","niar","noword"] # テストデータ write("参照テストを開始します。") write("開始:",&clock) every s := !L do { # テストデータを順次読み出し ss := csort(map(s)) # テストデータを、小文字変換し、ソートして writes(s,": ") # 変換前のデータを書き出し if member(T_dic,ss) # 辞書にあれば then { every writes(" ",!T_dic[ss]) # 辞書内容を書き出す write() } else write("辞書にありません。") } write("終了:",&clock) write("参照テストを終わりました。") 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から !で要素を取り出す時には、アルファベット順に取り出せる。 -----$ DICREF2.ICN ( lines:76 words:243 ) ------------------<cut here dicref2 >fff とすると、こういう結果になります。 辞書読込の際に、加工を していますので、読込時間が ４２秒に増えています。 -----^ FFF ( date:03-08-23 time:11:13 ) --------------------<cut here english.dic を読込中です。 開始:11:12:25 終了:11:13:07 english.dic の読込を終わりました。 257650 語ありました。 同一文字で構成される単語をまとめると、223704 種類となります。 参照テストを開始します。 開始:11:13:07 heavy: heavy Yahve rain: airn Arni Iran rain rani yveah: heavy Yahve niar: airn Arni Iran rain rani noword: 辞書にありません。 終了:11:13:07 参照テストを終わりました。 -----$ FFF ( lines:14 words:33 ) ---------------------------<cut here このプログラムでは、tableの値に listを入れていますが、Iconでは、tableの値に tableとか、listの値に tableや listとか、割と複雑なデータ構造を比較的簡単に 実現できます。 風つかい(hshinoh@mb.neweb.ne.jp) IconのWWWは、 http://www.cs.arizona.edu/icon/ UniconのWWWは、http://unicon.sourceforge.net/index.html BGM: Battery's not included ／ 森山威男＆杉本喜代志 (2003/08/23 TSfree6.txt) ■ TSfree > Iconミニ講座７（曖昧参照） 風つかい やめられない・止まらないエビセン体質のため、ついついミニ講座の続きを考えて しまいます。 曖昧検索を入れてみました。 コマンドラインから、英文文字列を指定して辞書検索を行いますが、'.'をワイルド カード (a-z)と見なせるようにしてみました。 '.'が２文字以上の場合は、"ab"と "ba"のようなものは、別に検索しないように 細工を入れました。 &lcaseは、英小文字に対応する組込キーワードです。 -----^ DICREFP2.ICN ( date:03-08-23 time:21:51 ) -----------<cut here #################### # 辞書読込・使用文字種毎の分類をした辞書参照で、曖昧検索対応。 #################### # dicrep2.icn Rev.1.0 2003/08/23 windy 風つかい H.S. #################### # Usage dicrefp2 英文字列(.はワイルドカード) # english.dicは、スペルチェック用の英単語が順に並んだもの。 # このプログラムのテストでは、DD SOFT SoundMixSpellコンポーネント # Ver 0.3.0 に 同梱の辞書ファイルを使用。 # This file is in the public domain. procedure main(args) # コマンドライン引数チェック。無ければ Usage表示 if *args < 1 then stop("dicrefp2 英単語 ( . はワイルドカード)") # 辞書読込 dic := "english.dic" # 辞書ファイル名 dir := open(dic) | stop(dic," が見つかりません") # 辞書ファイルオープン S_dic := set() # 辞書ダブリチェック用 set生成 T_dic := table() # 辞書格納 table生成 write(dic," を読込中です。") # 辞書読み込み write("開始:",&clock) n := 0 # 辞書行数カウンタ while word := read(dir) do { # 辞書を１行ずつ読み込んで、 n +:= 1 if n % 1000 = 0 then writes(&errout,"*") # 読み込み状況表示 if member(S_dic,word) then writes(&errout,"?") # 登録済みならエラー表示 else { insert(S_dic,word) # setに登録 # 単語を小文字変換しソートしたものをインデックスにして格納 # 同一文字を含む単語は同じインデックスに listの要素として格納される。 # ↓文字列ソート s_word := csort(map(word)) # 小文字へ変換し、ソートして # ↑小文字変換 if member(T_dic,s_word) # 辞書テーブルにあるかチェック then put(T_dic[s_word], word) # あれば、その listに追加 else T_dic[s_word] := [word] # 無ければ、listに入れて登録 } } close(dir) # 辞書ファイルクローズ write(&errout) write("終了:",&clock) write(dic," の読込を終わりました。 ",*S_dic," 語ありました。") write("同一文字で構\成される単語をまとめると、",*T_dic," 種類となります。") # ↑Shift-JISでは、0x5cを含むので、"\"を補完。 # 辞書参照テスト # コマンドラインの引数にて、辞書を参照 c_word := args[1] s_word := deletec(c_word,'.') # コマンドライン文字列から '.'を削除 n := *c_word -*s_word # '.'の数 n_comb := 0 # 組合せ数カウンタ n_find := 0 # 辞書にある件数カウンタ write(c_word," の組合せが辞書にあるかチェック中です。") write("開始:",&clock) every s := mscombd(string(&lcase),n) do { # ワイルドカード対応文字を取り出し n_comb +:= 1 # 組合せ数カウンタ＋１ ss := csort(map(s || s_word)) # コマンドライン引数の '.'以外の部分に足し # 小文字変換し、ソートして if member(T_dic,ss) # 辞書にあれば then { n_find +:= 1 # 辞書にある件数カウンタ＋１ writes(&errout,"!") # 発見表示 writes(ss,": ") # 変換前のデータを書き出し every writes(" ",!T_dic[ss]) # 辞書内容を書き出す write() } } write(&errout) write("終了:",&clock) write(n_comb," 通りの組合せのうち、",n_find," 通りが辞書にありました。") end ############################# # 文字列から重複して、ｎ個、降順のものを取り出す generator ############################# # arg [1]: string # [2]: integer # value : string # Usage : every ss := mscombd(s,n) do .. # ("abc",2) -> "aa","ab","ac","bb","bc","cc" procedure mscombd(s,n) if n =0 then return "" # 再帰終了 every i := 1 to *s do { # １～文字列長まで # ↓ i番目の文字を取り出して suspend s[i] || mscombd(s[i:0],n-1) } # ↑それ以降の文字と組み合わせる 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から !で要素を取り出す時には、アルファベット順に取り出せる。 #################### # strings.icnに含まれる 文字の削除 procedure #################### procedure deletec(s, c) #: delete characters local result # ローカル宣言（無くても良い） result := "" # 削除後の文字列格納エリア s ? { # sを走査対象として、 while result ||:= tab(upto(c)) do # cが見つかる迄の文字列を足し込んで tab(many(c)) # c以外の文字までスキップ return result ||:= tab(0) # 余りの文字を足し込む } end -----$ DICREFP2.ICN ( lines:123 words:404 ) ----------------<cut here dicrefp2 sunris. >ggg と、ワイルドカードを １ついれた場合は こんな結果になります。 -----^ GGG ( date:03-08-23 time:21:52 ) --------------------<cut here english.dic を読込中です。 開始:21:51:57 終了:21:52:40 english.dic の読込を終わりました。 257650 語ありました。 同一文字で構成される単語をまとめると、223704 種類となります。 sunris. の組合せが辞書にあるかチェック中です。 開始:21:52:40 ainrssu: Russian Surnias dinrssu: sundris einrssu: insures Serinus sunrise 終了:21:52:40 26 通りの組合せのうち、3 通りが辞書にありました。 -----$ GGG ( lines:12 words:25 ) ---------------------------<cut here 風つかい(hshinoh@mb.neweb.ne.jp) IconのWWWは、 http://www.cs.arizona.edu/icon/ UniconのWWWは、http://unicon.sourceforge.net/index.html BGM: 日本組曲 ／ 有馬徹とノーチェ・クバーナ with 杉本喜代志 (2003/08/23 TSfree7.txt) ■ TSfree > Iconミニ講座８（辞書分割） 風つかい 辞書にインデックスを付けて格納するようにしたせいで、辞書読込が４０秒以上に なってしまいました。 流石に、待ち時間がツライので、辞書から必要な字数の部分だけ、読み込むように しました。 辞書を、まず文字数毎のファイルに分割します。 辞書を、単語の文字数毎に、テーブルに読込みます。次に文字数毎のファイルに出力 します。 辞書のダブリチェックも入れて、出力ファイルはダブリを無くします。 english.dic T_dic +----------+ +-----------------------------+ |辞書 | |テーブル | |ファイル |--->|key:1 ->value:[a,i] |---> ファイル e01へ書き出し | | |key:2 ->value:[AA,Ab,AB,...] |---> ファイル e02へ書き出し +----------+ | | +-----------------------------+ -----^ DICDIV.ICN ( date:03-08-24 time:12:27 ) -------------<cut here #################### # 辞書を文字数毎に分割 #################### # dicdiv.icn Rev.1.0 2003/08/24 windy 風つかい H.S. #################### # Usage dicdiv dictionary_name # 辞書をファイル読込高速化のため、字数毎に分割するのに使用 # english.dicは、スペルチェック用の英単語が順に並んだもの。 # このプログラムのテストでは、DD SOFT SoundMixSpellコンポーネント # Ver 0.3.0 に 同梱の辞書ファイルを使用。 # This file is in the public domain. procedure main(args) if *args < 1 then stop("dicdiv dictionary_name") dic := args[1] # 辞書読込 dir := open(dic) | stop(dic," が見つかりません") # ファイルオープン n := 0 # ファイル行数カウンタ S_dic := set() # ダブリチェック用 set生成 T_dic := table() # 字数毎ファイル格納 table生成 write(&errout,dic," を読込中です。") # ファイル読み込み write(&errout,"開始:",&clock) while word := read(dir) do { # ファイルを１行ずつ読み込んで、 n +:= 1 if n % 1000 = 0 then writes(&errout,"*") # 読み込み状況表示 if member(S_dic,word) then writes(&errout,"?") # 登録済みならエラー表示 else { insert(S_dic,word) # setに登録 # 文字数を keyとしたテーブルに list形式で格納 if member(T_dic,*word) # テーブルにあるかチェック then put(T_dic[*word], word) # あれば、その listに追加 else T_dic[*word] := [word] # 無ければ、listに入れて登録 } } close(dir) # ファイルクローズ write(&errout) write(&errout,"終了:",&clock) write(&errout,dic," の読込を終わりました。 ",*S_dic," 語ありました。") # 字数毎辞書 書き出し write(&errout,"辞書の文字数別分割を始めます。") write(&errout,"開始:",&clock) every x := key(T_dic) do { # ↓右寄せ桁合わせ関数 f_out := dic[1] || right(x,2,"0") # 出力ファイル名： 元のファイル名の # 先頭１字＋字数 # ↓書込モードでファイルオープン dir := open(f_out,"w") | stop(f_out,"ファイルが開けません。") write(&errout,x,"字: ",f_out,": ",*T_dic[x]," 語あります。") every write(dir,!T_dic[x]) # x字の list要素を全て書き出し close(dir) } write(&errout,"終了:",&clock) write(&errout,"辞書の文字数毎の分割を終わりました。") end -----$ DICDIV.ICN ( lines:59 words:187 ) -------------------<cut here dicdiv english.dic としますと、次のように分割されます。 -----^ DIR.E ( date:03-08-24 time:12:41 ) ------------------<cut here ドライブ D: のボリュームラベルは DATA ボリュームシリアル番号は 112D-12DF ディレクトリは D:\2003\Unicon\TS_NW\CROSS\CROSS9 E01 6 03-08-24 12:28 E01 E02 1,444 03-08-24 12:28 E02 E03 9,070 03-08-24 12:28 E03 E04 35,286 03-08-24 12:28 E04 E05 87,381 03-08-24 12:28 E05 E06 172,848 03-08-24 12:28 E06 E07 286,461 03-08-24 12:28 E07 E08 386,510 03-08-24 12:28 E08 E09 425,040 03-08-24 12:28 E09 E10 399,012 03-08-24 12:28 E10 E11 329,615 03-08-24 12:28 E11 E12 248,346 03-08-24 12:28 E12 E13 176,520 03-08-24 12:28 E13 E14 122,784 03-08-24 12:28 E14 E15 79,084 03-08-24 12:28 E15 E16 49,194 03-08-24 12:28 E16 E17 29,716 03-08-24 12:28 E17 E18 17,500 03-08-24 12:28 E18 E19 9,093 03-08-24 12:28 E19 E20 3,916 03-08-24 12:28 E20 E21 1,932 03-08-24 12:28 E21 E22 912 03-08-24 12:28 E22 E23 450 03-08-24 12:28 E23 E24 338 03-08-24 12:28 E24 E25 54 03-08-24 12:28 E25 E27 29 03-08-24 12:28 E27 E28 30 03-08-24 12:28 E28 E29 31 03-08-24 12:28 E29 E30 32 03-08-24 12:28 E30 E31 33 03-08-24 12:28 E31 E32 34 03-08-24 12:28 E32 ENGLISH DIC 2,875,008 03-07-21 9:33 ENGLISH.DIC 32 個 5,747,709 バイトのファイルがあります. 0 ディレクトリ 1,183,285,248 バイトの空きがあります. -----$ DIR.E ( lines:39 words:177 ) ------------------------<cut here 一番長い単語は、３２文字で、dichlorodiphenyltrichloroethanes ですが、 なんという意味なんでしょうね。 辞書参照を、この分割辞書の必要なファイルだけ読み込むように、変更しました。 -----^ DICREFP3.ICN ( date:03-08-24 time:12:48 ) -----------<cut here #################### # 辞書読込・使用文字種毎の分類をした辞書参照で、曖昧検索対応。 #################### # dicrep3.icn Rev.1.0 2003/08/23 windy 風つかい H.S. #################### # Usage dicrefp3 英文字列(.はワイルドカード) # 文字数毎に分割された辞書ファイルを使用。 english.dicを分割。 # english.dicは、スペルチェック用の英単語が順に並んだもの。 # このプログラムのテストでは、DD SOFT SoundMixSpellコンポーネント # Ver 0.3.0 に 同梱の辞書ファイルを使用。 # This file is in the public domain. procedure main(args) # コマンドライン引数チェック。無ければ Usage表示 if *args < 1 then stop("dicrefp3 英単語 ( . はワイルドカード)") # 辞書読込 n_dic := *args[1] # 引数の文字数 # ↓右寄せ桁合わせ関数 dic := "e" || right(n_dic,2,"0") # 辞書ファイル名 dir := open(dic) | stop("その文字数の辞書は見つかりません") # 辞書ファイルオープン T_dic := table() # 辞書格納 table生成 write(" ",n_dic,"文字用辞書 ",dic," を読込中です。") # 辞書読み込み write("開始:",&clock) n := 0 # 辞書行数カウンタ while word := read(dir) do { # 辞書を１行ずつ読み込んで、 n +:= 1 if n % 1000 = 0 then writes(&errout,"*") # 読み込み状況表示 # 単語を小文字変換しソートしたものをインデックスにして格納 # 同一文字を含む単語は同じインデックスに listの要素として格納される。 # ↓文字列ソート s_word := csort(map(word)) # 小文字へ変換し、ソートして # ↑小文字変換 if member(T_dic,s_word) # 辞書テーブルにあるかチェック then put(T_dic[s_word], word) # あれば、その listに追加 else T_dic[s_word] := [word] # 無ければ、listに入れて登録 } close(dir) # 辞書ファイルクローズ write(&errout) write("終了:",&clock) write(" ",n_dic,"文字用辞書 ",dic," の読込を終わりました。",n," 語ありました。") write("同一文字で構\成される単語をまとめると、",*T_dic," 種類となります。") # ↑Shift-JISでは、0x5cを含むので、"\"を補完。 # 辞書参照テスト # コマンドラインの引数にて、辞書を参照 c_word := args[1] s_word := deletec(c_word,'.') # コマンドライン文字列から '.'を削除 n := *c_word -*s_word # '.'の数 n_comb := 0 # 組合せ数カウンタ n_find := 0 # 辞書にある件数カウンタ write(c_word," の組合せが辞書にあるかチェック中です。") write("開始:",&clock) every s := mscombd(string(&lcase),n) do { # ワイルドカード対応文字を取り出し n_comb +:= 1 # 組合せ数カウンタ＋１ ss := csort(map(s || s_word)) # コマンドライン引数の '.'以外の部分に足し # 小文字変換し、ソートして if member(T_dic,ss) # 辞書にあれば then { n_find +:= 1 # 辞書にある件数カウンタ＋１ writes(&errout,"!") # 発見表示 writes(ss,": ") # 変換前のデータを書き出し every writes(" ",!T_dic[ss]) # 辞書内容を書き出す write() } } write(&errout) write("終了:",&clock) write(n_comb," 通りの組合せのうち、",n_find," 通りが辞書にありました。") end ############################# # 文字列から重複して、ｎ個、降順のものを取り出す generator ############################# # arg [1]: string # [2]: integer # value : string # Usage : every ss := mscombd(s,n) do .. # ("abc",2) -> "aa","ab","ac","bb","bc","cc" procedure mscombd(s,n) if n =0 then return "" # 再帰終了 every i := 1 to *s do { # １～文字列長まで # ↓ i番目の文字を取り出して suspend s[i] || mscombd(s[i:0],n-1) } # ↑それ以降の文字と組み合わせる 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から !で要素を取り出す時には、アルファベット順に取り出せる。 #################### # strings.icnに含まれる 文字の削除 procedure #################### procedure deletec(s, c) #: delete characters local result # ローカル宣言（無くても良い） result := "" # 削除後の文字列格納エリア s ? { # sを走査対象として、 while result ||:= tab(upto(c)) do # cが見つかる迄の文字列を足し込んで tab(many(c)) # c以外の文字までスキップ return result ||:= tab(0) # 余りの文字を足し込む } end -----$ DICREFP3.ICN ( lines:120 words:401 ) ----------------<cut here （追記 mscombdという命名は間違っていますね。最後の dは降順という意味なの ですが、ご覧の通り、ソートを一切かけていませんので、降順にはなりません。 この procedureに対する名前は、mscombが正しいのです。） dicrefp3 mi.nigh. >hhh とすると、次のような結果になります。 だいぶ、辞書読込時間が短くなりました。 -----^ HHH ( date:03-08-24 time:14:13 ) --------------------<cut here 8文字用辞書 e08 を読込中です。 開始:14:13:51 終了:14:13:54 8文字用辞書 e08 の読込を終わりました。38651 語ありました。 同一文字で構成される単語をまとめると、32836 種類となります。 mi.nigh. の組合せが辞書にあるかチェック中です。 開始:14:13:54 acghiimn: Michigan cghiimnr: chirming cghiimns: michings cghiimnt: mitching dghiimnt: midnight ghiimmns: shimming ghiimmnw: whimming ghiimnnu: inhuming ghiimnst: smithing 終了:14:13:54 351 通りの組合せのうち、9 通りが辞書にありました。 -----$ HHH ( lines:18 words:36 ) ---------------------------<cut here 風つかい(hshinoh@mb.neweb.ne.jp) IconのWWWは、 http://www.cs.arizona.edu/icon/ UniconのWWWは、http://unicon.sourceforge.net/index.html BGM: Battery's not included ／ 森山威男＆杉本喜代志 (2003/08/24 TSfree8.txt) ■ TSfree > Iconミニ講座９（分配組合せ） 風つかい 文字列で、辞書参照をするときに、文字の組合せを作ろうと思うのですが、例えば ４文字 "abcd" とあって、組合せのプログラムを書くと例えば、こうなります。 -----^ PCOMB1.ICN ( date:03-08-25 time:20:43 ) -------------<cut here #################### # 文字列分配プログラムの習作１ #################### # pcomb1.icn Rev.1.0 2003/08/25 windy 風つかい H.S. #################### # This file is in the public domain. procedure main() L := [[4],[3,1],[2,2],[2,1,1],[1,1,1,1]] # 文字列分配パターン（文字数） s := "abcd" # テスト文字列 write(s) every LL := !L do { # 分配文字数パターンから順次取り出して、 write("---") # 表示用 every LLL := pcomb(s,LL) do { # 分配結果を順次取り出して、 writes(" ->") # 表示用 every writes(" ",!LLL) # 出力する。 write() } } end #################### # 分配の組合せ #################### # arg [1]: string 分配する英文字列：分配パターンのトータルに合ってること。 # [2]: list 分配パターン（降順の list） # value : list 分割された文字列 # Usage : every LL := pcomb(s,L) do .. # ("abc",[2,1]) -> ["ab","c"],["ac","b"],["bc","a"] # 同一分配数が複数ある場合は、無駄が生じる。 # 例：("abcd",[2,2])の場合に、["ab","cd"] と ["cd","ab"]の両方が出る。 procedure pcomb(s,L) if *L = 1 then return [s] # 再帰終了 if L[1] = 1 then { # 後は、順に１文字ずつ listに入れるだけ return [s[1]] ||| pcomb(s[2:0], L[2:0]) # } # ↑先頭文字 ↑残り文字列 ↑残りのリスト # ２文字以上の指定ならば、 every ss := scomb(s,L[1]) do { # 文字の組合せを作って suspend [ss] ||| pcomb(ssub(s,ss),L[2:0]) # 残りの文字のため再帰 } # ↑組合せ文字 ↑残り文字列 ↑残りのリスト end #################### # 文字列の引き算 #################### # arg [1]: string 被削除文字列 # [2]: string 削除文字列 # value : string 結果文字列 # 文字列 s1の先頭から、文字列 s2の文字を削除。１：１で削除。 # ("abcabc","abd") -> "cabc" s1に無い文字は無視される。 procedure ssub(s1,s2) every c := !s2 do { # s2から１文字ずつ取り出して ss := "" # 上記文字を削除後の文字列の格納エリア s1 ? { # s1を走査対象として、 if ss ||:= tab(upto(c)) then { # 文字が見つかれば そこ迄の文字列を # ssに足し込み move(1) # １文字スキップ ss ||:= tab(0) # 残りの文字列を足し込み s1 := ss # s1更新 } } } return s1 end #################### # 文字列の nCm (n = *s) n個文字列から、m文字を選ぶ。 generator #################### # 1998/04/16 windy 名称変更 comb -> scomb (BIPLとダブルので） # stringの組み合わせ # nCm (n = *s) n個のものから、m個を選ぶ。 # arg: [1]: s: string # [2]: m: integer # value: string # Usage: every ss := scomb(s,m) do ... # Icon入門講座３（１１） procedure scomb(s,m) /m := *s # デフォルト nCn (n = m = *s) if m = 0 then return "" # mを文字数カウンターに使う。 # ０なったら、そこで打ち止め。 suspend s[i := 1 to *s] || scomb(s[i+1 : 0], m -1) #↑ １文字選ぶ ↑ ↑←前で選んだ文字以降 ↑指定文字数に # ｜ の文字列に対し同じ 文字列を抑え # ｜ 処理を行う。 るためのカウ # 文字列の連結 ンター end -----$ PCOMB1.ICN ( lines:88 words:334 ) -------------------<cut here pcomb1 > iii とすると、こうなります。 -----^ III ( date:03-08-25 time:20:45 ) --------------------<cut here abcd --- -> abcd --- -> abc d -> abd c -> acd b -> bcd a --- -> ab cd -> ac bd -> ad bc -> bc ad -> bd ac -> cd ab --- -> ab c d -> ac b d -> ad b c -> bc a d -> bd a c -> cd a b --- -> a b c d -----$ III ( lines:24 words:67 ) ---------------------------<cut here 結果を見てみますと、同じ文字数を連続して取り出す（２文字を２回）時に、 ["ab","cd"] と ["cd","ab"]が、両方でてきます。 これは、片方だけで良いのです。 よく見ると、不要なケースは、結果の 並びが、降順になっていないケースみたいです。 そこで、降順の組合わせだけ 取り出すように、修正してみました。 文字列の比較式で、<< という記号が出てきますが、これは文字列が辞書順で 先か後かの比較を行うものです。 文字列組合せの scombが、同一文字指定に対応していませんでしたので、対応する exscombを作りました。 -----^ PCOMB2.ICN ( date:03-08-25 time:20:44 ) -------------<cut here #################### # 文字列分配プログラムの習作２ #################### # pcomb2.icn Rev.1.0 2003/08/25 windy 風つかい H.S. #################### # This file is in the public domain. procedure main() L := [[4],[3,1],[2,2],[2,1,1],[1,1,1,1]] # 文字列分配パターン（文字数） s := "abcd" # テスト文字列 write(s) every LL := !L do { # 分配文字数パターンから順次取り出して、 write("---") # 表示用 every LLL := expcomb(s,LL) do { # 分配結果を順次取り出して、 writes(" ->") # 表示用 every writes(" ",!LLL) # 出力する。 write() } } end #################### # 分配の組合せ #################### # arg [1]: string 分配する英文字列：分配パターンのトータルに合ってること。 # [2]: list 分配パターン（降順の list） # [3]: string 前の文字列（同一文字数指定の場合に降順のものだけ選ぶための） # value : list 分割された文字列（ listに格納） # Usage : every LL := expcomb(s,L) do .. # ("abc", [2,1]) -> ["ab","c"], ["ac","b"], ["bc","a"] # ("abcd",[2,2]) -> ["ab","cd"],["ac","bd"],["ad","bc"] procedure expcomb(s,L,s_ref) /s_ref := "" # 指定なければ、空文字 s := csort(s) # 文字列ソート if *L = 1 then { # パターン要素の最後で、 if L[1] = *s_ref then { # 前回と文字数が同じで、 if s << s_ref then return &fail # 辞書順で前なら、失敗させる。 } return [s] # ↑で、無ければ、文字列を返す。 } # １文字の文字列指定ならば、後は、順に１文字ずつ listに入れるだけ if L[1] = 1 then { # １文字の文字列指定ならば、 # 後は、順に１文字ずつ listに入れるだけ return [s[1]] ||| expcomb(s[2:0], L[2:0]) } # ↑先頭文字 ↑残り文字列 ↑残りのリスト # ２文字以上の文字列指定ならば、 every ss := exscomb(s,L[1]) do { # 文字の組合せを作って if *ss = *s_ref then { # 前回と文字数が同じで、 if ss << s_ref then return &fail # 辞書順で前なら、失敗させる。 } # ↓参照用文字列 suspend [ss] ||| expcomb(ssub(s,ss),L[2:0],ss) } # ↑組合せ文字 ↑残り文字列 ↑残りのリスト end #################### # 文字列の引き算 #################### # arg [1]: string 被削除文字列 # [2]: string 削除文字列 # value : string 結果文字列 # 文字列 s1の先頭から、文字列 s2の文字を削除。１：１で削除。 # ("abcabc","abd") -> "cabc" s2にある文字で、s1に無い文字は無視される。 procedure ssub(s1,s2) every c := !s2 do { # s2から１文字ずつ取り出して ss := "" # 上記文字を削除後の文字列の格納エリア s1 ? { # s1を走査対象として、 if ss ||:= tab(upto(c)) then { # 文字が見つかれば そこ迄の文字列を # ssに足し込み move(1) # １文字スキップ ss ||:= tab(0) # 残りの文字列を足し込み s1 := ss # s1更新 } } } return s1 end #################### # 文字列の nCm (n = *s) n個文字列から、m文字を選ぶ。 generator #################### # stringの組み合わせ # nCm (n = *s) n個のものから、m個を選ぶ。 # arg: [1]: s: string # [2]: m: integer # value: string # Usage: every ss := exscomb(s,m) do ... # Icon入門講座３（１１）scomb()を同一文字指定対応に拡張 procedure exscomb(s,m) initial { s := csort(s) # 文字列をソートする。(BIPL:strings.icn) /m := *s # デフォルト nCn (n = m = *s) } if m = 0 then return "" # mを文字数カウンターに使う。 # ０なったら、そこで打ち止め。 suspend s[i := new_pos(s)] || exscomb(s[i+1 : 0], m -1) #↑ １文字選ぶ ↑ ↑←前で選んだ文字以降 ↑指定文字数に # ｜ の文字列に対し同じ 文字列を抑え # ｜ 処理を行う。 るためのカウ # 文字列の連結 ンター 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から !で要素を取り出す時には、アルファベット順に取り出せる。 -----$ PCOMB2.ICN ( lines:136 words:501 ) ------------------<cut here pcomb2 > jjj とするとこうなります。２文字を２回取り出す所での重複がなく なりました。 なんとか、ケースを減らせたみたいです。 -----^ JJJ ( date:03-08-25 time:20:44 ) --------------------<cut here abcd --- -> abcd --- -> abc d -> abd c -> acd b -> bcd a --- -> ab cd -> ac bd -> ad bc --- -> ab c d -> ac b d -> ad b c -> bc a d -> bd a c -> cd a b --- -> a b c d -----$ JJJ ( lines:21 words:58 ) ---------------------------<cut here 風つかい(hshinoh@mb.neweb.ne.jp) IconのWWWは、 http://www.cs.arizona.edu/icon/ UniconのWWWは、http://unicon.sourceforge.net/index.html BGM: 蝉の声 ／ 近所の蝉たち (2003/08/25 Ts_free9.txt) ■ TSfree > Iconミニ講座１０（分割文字で辞書参照） 風つかい さて、まとめで、フルスペックのプログラムにまとめましょう。 ・入力文字列を分割したもので、辞書参照。 ・不明文字対応のため、曖昧検索指定。 ・辞書は、文字数別に分割し、必要なものだけ使う。 辞書分割の際にダブリチェックして、分割後の辞書ファイルには ダブリが無いので、このプログラムでは単語のダブリチェックは 削除します。 というところで、まとめると次のようになります。 尚、試して頂きやすいように、全ての procedureを１つのファイルにしていますが、 サブ procedureを、別のファイルにして、mainファイルから linkするようにもでき ます。 -----^ DICREFP5.ICN ( date:03-08-25 time:20:05 ) -----------<cut here #################### # 文字列の組合せで、辞書参照。曖昧検索。分割辞書。ワイルドカード未対応 #################### # dicrefp5.icn Rev.1.0 2003/08/25 windy 風つかい H.S. #################### # Usage dicrefp5 英文字列(.はワイルドカード) # 文字数毎に分割された辞書ファイルを使用。 english.dicを分割。 # english.dicは、スペルチェック用の英単語が順に並んだもの。 # このプログラムのテストでは、DD SOFT SoundMixSpellコンポーネント # Ver 0.3.0 に 同梱の辞書ファイルを使用。 # This file is in the public domain. procedure main(args) # コマンドライン引数チェック。無ければ Usage表示 if *args < 1 then stop("dicrefp5 英単語(.はワイルドカード)", " 最大分割数 最小文字長") # コマンドラインの引数から、辞書を読込 c_word := args[1] # コマンドラインの英文字列 ndiv := \args[2] | 1 # 分割数指定無しは、１（分割せず） nmin := \args[3] | *c_word # 最小文字長指定無しは、引数文字列長 # 分割パターン格納 L_lpat := [] # 文字列分割パターン格納 list every put(L_lpat,n_divdf(*c_word,ndiv,nmin)) # 分割パターン格納 # 必要な文字数に対応する辞書の読込 S_pat := set() # 文字数格納 set（指定文字数辞書読込のため） every L := !L_lpat do every insert(S_pat,!L) # 文字数を全て 格納 T_dic := table() # 辞書格納 table生成 every n_pat := !S_pat do { # ↓右寄せ桁合わせ関数 dic := "e" || right(n_pat,2,"0") # 辞書ファイル名 dir := open(dic) | stop(" ",n_pat,"文字用の辞書が見つかりません。") # 辞書ファイルオープン writes(" ",n_pat,"文字用辞書 ",dic," を読込中です。開始:",&clock) n := 0 # 辞書行数カウンタ while word := read(dir) do { # 辞書を１行ずつ読み込んで、 n +:= 1 if n % 1000 = 0 then writes(&errout,"*") # 読み込み状況表示 # 単語を小文字変換しソートしたものをインデックスにして格納 # 同一文字を含む単語は同じインデックスに listの要素として格納される。 # ↓文字列ソート s_word := csort(map(word)) # 小文字へ変換し、ソートして # ↑小文字変換 if member(T_dic,s_word) # 辞書テーブルにあるかチェック then put(T_dic[s_word], word) # あれば、その listに追加 else T_dic[s_word] := [word] # 無ければ、listに入れて登録 } close(dir) # 辞書ファイルクローズ write(&errout) write(" 終了:",&clock," ",n,"語ありました。") } write("\n",c_word," を、最大分割数 ",ndiv,"、最小文字長 ",nmin, " にて分割してチェック。開始:",&clock) # 辞書参照 n_comb := 0 # 組合せ数カウンタ n_find := 0 # 辞書にある件数カウンタ s_word := deletec(c_word,'.') # コマンドライン文字列から '.'を削除 n_dot := *c_word -*s_word # '.'の数 # ↓英小文字 every s_wild := mscombd(string(&lcase),n_dot) do { # ワイルドカード文字を、 s_check := s_wild || map(s_word) # コマンドライン引数の '.'以外に足し、 every Lpat:= !L_lpat do { # 分配文字数パターンから順次取り出して、 every Lword := expcomb(s_check,Lpat) do { # 分配結果を順次取り出して、 n_comb +:= 1 # チェック回数カウンタ＋１ if n_comb % 1000 = 0 then writes(&errout,"*") # チェック状況表示 ERR := &null # 辞書参照エラーフラッグリセット Llresult := [] # 辞書検索結果格納 list every (ss := !Lword) & /ERR do { # 細分文字を取り出して、 # ↑既に辞書参照エラーが発生していなければ、 # 細分文字が辞書に存在するかチェック if member(T_dic,ss) then put(Llresult,T_dic[ss]) # 結果データ格納 else ERR := "ERR" # 参照エラーフラッグセット } # 細分文字列が全て辞書にあれば、書き出し if /ERR then { # エラーフラッグが立っていなければ n_find +:= 1 # カウンタ＋１ writes(&errout,"!") # 合致表示 writes(s_word) # if *s_wild >= 1 then writes(" + ",s_wild) writes(" ->") # nn := 0 # 細分文字群カウンタ every Lstr := !Llresult do { # 細分文字群を取り出して nn +:= 1 # カウンタ＋１ if nn > 1 then writes(" +") # 先頭でなければ、区切りマーク every writes(" ",!Lstr) # 文字群を書き出し } write() } } } } write(&errout) write(n_comb," 通りの組合せのうち、",n_find," 通りが辞書にありました。", " 終了:",&clock) end #################### # 分配の組合せ #################### # arg [1]: string 分配する英文字列：分配パターンのトータルに合ってること。 # [2]: list 分配パターン（降順の list） # [3]: string 前の文字列（同一文字数指定の場合に降順のものだけ選ぶための） # value : list 分割された文字列（ listに格納） # Usage : every LL := expcomb(s,L) do .. # ("abc", [2,1]) -> ["ab","c"], ["ac","b"], ["bc","a"] # ("abcd",[2,2]) -> ["ab","cd"],["ac","bd"],["ad","bc"] procedure expcomb(s,L,s_ref) /s_ref := "" # 指定なければ、空文字 s := csort(s) # 文字列ソート if *L = 1 then { # パターン要素の最後で、 if L[1] = *s_ref then { # 前回と文字数が同じで、 if s << s_ref then return &fail # 辞書順で前なら、失敗させる。 } return [s] # ↑で、無ければ、文字列を返す。 } # １文字の文字列指定ならば、後は、順に１文字ずつ listに入れるだけ if L[1] = 1 then { # １文字の文字列指定ならば、 # 後は、順に１文字ずつ listに入れるだけ return [s[1]] ||| expcomb(s[2:0], L[2:0]) } # ↑先頭文字 ↑残り文字列 ↑残りのリスト # ２文字以上の文字列指定ならば、 every ss := exscomb(s,L[1]) do { # 文字の組合せを作って if *ss = *s_ref then { # 前回と文字数が同じで、 if ss << s_ref then return &fail # 辞書順で前なら、失敗させる。 } # ↓参照用文字列 suspend [ss] ||| expcomb(ssub(s,ss),L[2:0],ss) } # ↑組合せ文字 ↑残り文字列 ↑残りのリスト end #################### # 文字列の引き算 #################### # arg [1]: string 被削除文字列 # [2]: string 削除文字列 # value : string 結果文字列 # 文字列 s1の先頭から、文字列 s2の文字を削除。１：１で削除。 # ("abcabc","abd") -> "cabc" s2にある文字で、s1に無い文字は無視される。 procedure ssub(s1,s2) every c := !s2 do { # s2から１文字ずつ取り出して ss := "" # 上記文字を削除後の文字列の格納エリア s1 ? { # s1を走査対象として、 if ss ||:= tab(upto(c)) then { # 文字が見つかれば そこ迄の文字列を # ssに足し込み move(1) # １文字スキップ ss ||:= tab(0) # 残りの文字列を足し込み s1 := ss # s1更新 } } } return s1 end #################### # 文字列の nCm (n = *s) n個文字列から、m文字を選ぶ。 generator #################### # stringの組み合わせ # nCm (n = *s) n個のものから、m個を選ぶ。 # arg: [1]: s: string # [2]: m: integer # value: string # Usage: every ss := exscomb(s,m) do ... # Icon入門講座３（１１）scomb()を同一文字指定対応に拡張 procedure exscomb(s,m) initial { s := csort(s) # 文字列をソートする。(BIPL:strings.icn) /m := *s # デフォルト nCn (n = m = *s) } if m = 0 then return "" # mを文字数カウンターに使う。 # ０なったら、そこで打ち止め。 suspend s[i := new_pos(s)] || exscomb(s[i+1 : 0], m -1) #↑ １文字選ぶ ↑ ↑←前で選んだ文字以降 ↑指定文字数に # ｜ の文字列に対し同じ 文字列を抑え # ｜ 処理を行う。 るためのカウ # 文字列の連結 ンター 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 ############################# # 文字列から重複して、ｎ個、降順のものを取り出す generator ############################# # arg [1]: string # [2]: integer # value : string # Usage : every ss := mscombd(s,n) do .. # ("abc",2) -> "aa","ab","ac","bb","bc","cc" procedure mscombd(s,n) if n =0 then return "" # 再帰終了 every i := 1 to *s do { # １～文字列長まで # ↓ i番目の文字を取り出して suspend s[i] || mscombd(s[i:0],n-1) } # ↑それ以降の文字と組み合わせる 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 # 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から !で要素を取り出す時には、アルファベット順に取り出せる。 #################### # strings.icnに含まれる 文字の削除 procedure #################### procedure deletec(s, c) #: delete characters local result # ローカル宣言（無くても良い） result := "" # 削除後の文字列格納エリア s ? { # sを走査対象として、 while result ||:= tab(upto(c)) do # cが見つかる迄の文字列を足し込んで tab(many(c)) # c以外の文字までスキップ return result ||:= tab(0) # 余りの文字を足し込む } end -----$ DICREFP5.ICN ( lines:290 words:1124 ) ---------------<cut here （追記 コメントの 「ワイルドカード未対応」は、削除漏れです。ワイルドカード に対応しています。） 曖昧検索指定が無い場合の例をを１つ。 dicrefp5 heavyrain 2 4 >kkk としますと、次のようになります。 -----^ KKK ( date:03-08-25 time:20:56 ) --------------------<cut here 5文字用辞書 e05 を読込中です。開始:20:56:50 終了:20:56:50 12483語ありました。 4文字用辞書 e04 を読込中です。開始:20:56:50 終了:20:56:51 5881語ありました。 9文字用辞書 e09 を読込中です。開始:20:56:51 終了:20:56:55 38640語ありました。 heavyrain を、最大分割数 2、最小文字長 4 にて分割してチェック。開始:20:56:55 heavyrain -> rayah + nevi vein vine heavyrain -> Aryan + hive heavyrain -> hiera + navy Navy heavyrain -> haven + airy Iyar heavyrain -> hyena + riva vair heavyrain -> haver + ayin heavyrain -> hayer + vain vina heavyrain -> heavy Yahve + airn Arni Iran rain rani heavyrain -> raven + hiya Yahi heavyrain -> hairy + Evan nave vane vena heavyrain -> Invar invar ravin Vanir + yeah heavyrain -> rainy + have heavyrain -> hiver + Yana heavyrain -> nervi riven viner + ayah heavyrain -> veiny + haar 92 通りの組合せのうち、15 通りが辞書にありました。 終了:20:56:55 -----$ KKK ( lines:21 words:119 ) --------------------------<cut here さて不明文字が２つあるケースだと、 dicrefp5 a.ahviy.r 2 4 >lll としますと、こんな結果になります。 -----^ LLL ( date:03-08-25 time:20:59 ) --------------------<cut here 5文字用辞書 e05 を読込中です。開始:20:59:10 終了:20:59:10 12483語ありました。 4文字用辞書 e04 を読込中です。開始:20:59:10 終了:20:59:11 5881語ありました。 9文字用辞書 e09 を読込中です。開始:20:59:11 終了:20:59:15 38640語ありました。 a.ahviy.r を、最大分割数 2、最小文字長 4 にて分割してチェック。開始:20:59:15 aahviyr + aa -> Avahi + raya aahviyr + aa -> varia + ayah aahviyr + ab -> Bahai + vary aahviyr + ab -> brava + hiya Yahi aahviyr + ab -> Avahi + bray Brya （中略） aahviyr + en -> hayer + vain vina aahviyr + en -> heavy Yahve + airn Arni Iran rain rani aahviyr + en -> raven + hiya Yahi aahviyr + en -> hairy + Evan nave vane vena aahviyr + en -> Invar invar ravin Vanir + yeah （中略） aahviyr + uy -> hairy + Vayu aahviyr + vx -> hyrax + viva aahviyr + wy -> hairy + wavy aahviyr + xx -> rayah + xxiv XXIV xxvi XXVI aahviyr + xz -> varix + hazy 27602 通りの組合せのうち、943 通りが辞書にありました。 終了:20:59:20 -----$ LLL ( lines:949 words:7467 ) ------------------------<cut here 結構、合致するものがありますので、途中を略してあります。 ９４３件だと結果のチェックに時間がかかりそうです。 ちょっと長引きましたが、ちょうど１０回目ということで、Iconミニ講座は、 終わりにします。（宣言しておかないと、すぐまた続けそうなので。笑） 長文におつき合い頂きまして、有り難うございます。 風つかい(hshinoh@mb.neweb.ne.jp) IconのWWWは、 http://www.cs.arizona.edu/icon/ UniconのWWWは、http://unicon.sourceforge.net/index.html BGM: Hello It's Me / Lani Hall (2003/08/25 TSfreeA.txt) ■ TSfree > Iconミニ講座 おまけ（プログラムの整理） 風つかい 何かのプログラムを作っても、しばらく経つと、作った自分でも、「一体何のための プログラムだっけ？」とか「一体何のためにこういう処理にしてるんだろう？」と悩む ことが沢山あります。 私のハードディスクには、そんな正体不明のプログラムがあふれています。 今後も使えそうな procedureはライブラリーにして、独立プログラムはコメントを 充実して保管したい。とは、思っていますが、なかなかできないですね。 今回は、少しやっておこうと思います。 また、少し Iconの特徴を生かしていない 部分がありますので、書き直してみました。 ＜書き直し１＞ if member(T_dic,s_word) # 辞書テーブルにあるかチェック then put(T_dic[s_word], word) # あれば、その listに追加 else T_dic[s_word] := [word] # 無ければ、listに入れて登録 という部分があります。 辞書 tableには、例えば key:"abc" に対応した 値として、ソートして小文字化 すると"abc"となる単語を登録します。 そういう単語は複数ある可能性がありますので、key:"abc"に対応する 値は list として、その中に 順次追加していきます。 <1>最初 値に "ABC"を追加 key:"abc" -> ["ABC"] としたい。 ・・・key:"abc"が無い状態から追加 <2>次は 値に "BcA"を追加 key:"abc" -> ["ABC","BcA"] としたい。 ・・・既に key:"abc"に対応する要素 "ABC"があって更に "BcA"を追加 <1>の状態（key:"abc"が無い状態）で、key:"abc"の値に listがあるつもりで <2>と同じやり方で、単語を追加しようと listへの追加処理をすると、該当する keyが無いということで、エラーが発生します。 put(T_dic[s_word],word) は、エラーが発生。 （ランタイムエラー：存在しない値(&null)にアクセスしようとした。） （補足：listの追加処理で、追加先の listが無いというエラーも発生する条件だが、 tableの keyが無いというエラーが先だと思います。） <2>の状態なら key:"abc"は存在して、値には list ["ABC"]が存在していますので、 このlistへの追加処理で単語が追加できます。 put(T_dic[s_word],word) で、単語が追加できる。 <1>の状態（key:"abc"が無い状態）で値に単語を追加する場合は、 T_dic["abc"] := ["ABC"]で、 key:"abc"の値に要素数１の listをセット しなければいけません。 この<1>と<2>処理の違いを if..then..else..で分けています。 さて、（key:"abc"が無い状態）をチェックするには、member(T_dic,"abc")で できますが、実際に key:"abc"で tableにアクセス(T_dic["abc"])してエラーが 発生するかどうかでもチェックできます。 でも、ランタイムエラーが発生するとプログラムが止まってしまいます。 それでは困るので、Iconには、存在しない(&null)かどうかを判定する仕掛け があります。 \T_dic["abc"] は、存在すれば key:"abc"に対応する T_dicの値を、 存在しなければ、&fail（エラー状態）となり、 ランタイムエラーにはなりません。 そこで、if member(T_dic,s_word) は、if \T_dic[s_word] とできますので、 if \T_dic[s_word] # 辞書テーブルにあるかチェック then put(T_dic[s_word], word) # あれば、その listに追加 else T_dic[s_word] := [word] # 無ければ、listに入れて登録 と、書き直せます。 key:"abc"が無い状態では、 put(T_dic["abc"],word)は、ランタイムエラーを発生しますが、 put(\T_dic[["abc"],word)は、ランタイムエラーを発生せず failして、 値は、&failとなります。 そこで、更に、if .. then .. else ..式を、 put(\T_dic[s_word],word) | (T_dic[s_word] := [word]) と、１行にできます。 "|"の左辺が failした場合は、右辺の式が生きて、 (T_dic[s_word] := [word])を実行する動作となり、if .. then .. else .. と 同等の動作となります。 ＜書き直し２＞ ERR := &null # 辞書参照エラーフラッグリセット Llresult := [] # 辞書検索結果格納 list every (ss := !Lword) & /ERR do { # 細分文字を取り出して、 # ↑既に辞書参照エラーが発生していなければ、 # 細分文字が辞書に存在するかチェック if member(T_dic,ss) then put(Llresult,T_dic[ss]) # 結果データ格納 else ERR := "ERR" # 参照エラーフラッグセット } ここは、分解した文字列の各々が辞書に存在するかのチェックをしています。 ERR というフラッグを立てているのが、美しくありません。 これは、辞書 table参照用の別 procedureを作ると、 Llresult := tbl_ref(T_dic,Lword) | &null # 分配文字列が全て辞書にあれば 辞書参照結果をセット。 # いずれかが辞書になければ、&nullでクリア。 と、一行にできます。 このように、Iconでは "|"を使うと、表記がコンパクトになる場合があります。 ＜書き直しその他＞ 共通的な procedureは、別ファイルにして、メインファイルから linkするように してみました。 また変数名は若干変更してあります。 procedure名も１つ統一が 取れてなかったので修正しました。 link指定は、私のライブラリ区分に従っていましたが、お試しになる場合を考えて 元のファイルから必要な部分だけ抜粋したファイルを作成し、それを linkしてあり ます。 ライブラリを、icont -c foo.icn と、予めコンパイルして、中間コード化 しておき、 その後に、 icont decrefp6.icn と、すれば実行ファイルが作成できます。 -----^ DICREFP6.ICN ( date:03-08-29 time:23:15 ) -----------<cut here #################### # クロスワードパズル支援 #################### # dicrefp6.icn Rev.1.1 2003/08/29 windy 風つかい H.S. #################### # クロスワードパズル支援 # ・英文字のクロスワードパズルをまず解いて、その後指定の升目の文字を # 組み合わせて最終的な単語を見つける。 # ・一部判っていない升目がある。 # ・辞書ファイルを参照。英語の単語がズラッと並んだ形式の辞書ファイル。 # ・例： 判らない文字を .で表すと、a.ahviy.r となる。 # この場合の正解（例）は、heavy rain という２つの単語の組合せ。 # 補足 # ・コマンドライン引数から、文字列を生成して、辞書を参照し、辞書にあれば出力。 # 不明文字のための曖昧検索。単語組合せのため文字列分割。 # ・辞書参照時間短縮のため、辞書を読み込む時に、単語を文字ソート・小文字変換 # した keyをつけて、tableに格納。 この tableを参照。 # ・辞書読込時間短縮のため、文字数毎に分割された辞書ファイルから必要な字数の # ファイルのみを読込む。 # 元の辞書(english.dic)は、スペルチェック用の英単語が順に並んだもの。 # このプログラムのテストでは、DD SOFT SoundMixSpellコンポーネント # Ver 0.3.0 に 同梱の辞書ファイルを使用。 # ・辞書は、予め文字数毎に、e01,e02,...等に分割しておく。（別プログラム） # ・TS Network TSabc,TSfree関連 # 履歴 # dicrefp5.icnを修正。サブ procedureを link形式にした。 # 条件式 変数名 を見直し。訂正: mscombd -> mscomb procedure名の付与ミス # This file is in the public domain. link file_x, # ファイル関係 f_name: 実行ファイル名取得 string_x, # 文字列関係 mscomb: 英文字列重複組合せ # expcomb: 英文字列分配組合せ number_x, # 数字関係 ndivdf: 正整数の部分和(降順 分割数・最小制限) stringsx # 文字列関係（Icon基本ライブラリ BIPLに含まれるもの） # deletec: 英文字列から文字を削除 # csort: 英文字列の辞書順ソート procedure main(args) # コマンドライン引数チェック。無ければ Usage表示 Usage := " 英単語(.はワイルドカード) 最大分割数 最短文字長" if *args < 1 then stop(f_name(),Usage) c_word := args[1] # コマンドラインの英文字列 # ↓左辺の式が失敗すれば、右辺の式を選ぶ ndiv := \args[2] | 1 # 分割数指定無しは、１（分割せず） nmin := \args[3] | *c_word # 最小文字長指定無しは、引数文字列長 # コマンドライン引数から、分割パターンを生成 L_lpat := [] # 文字列分割パターン格納 list every put(L_lpat,n_divdf(*c_word,ndiv,nmin)) # 分割パターン格納 # L_lpat例:[[6],[3,3]] # 必要な文字数の生成（ setに入れて、ダブリを削除） S_pat := set() # 文字数格納 set（指定文字数ため） every L := !L_lpat do every insert(S_pat,!L) # 文字数を全て 格納 # S_pat例: (6,3) T_dic := table() # 辞書格納 table生成 every n_pat := !S_pat do { # 辞書ファイル名生成 # ↓rightは、右寄せ桁合わせ関数 dic := "e" || right(n_pat,2,"0") # 辞書ファイル名 例:"e06","e03" # 辞書ファイルオープン dir := open(dic) | stop(" ",n_pat,"文字用の辞書が見つかりません。") writes(" ",n_pat,"文字用辞書 ",dic," を読込中です。開始:",&clock) # 辞書読込 n_line := 0 # 辞書行数カウンタ # 辞書を１行ずつ読み込んで、 while word := read(dir) do { n_line +:= 1 # 辞書行数＋１ if n_line % 1000 = 0 then writes(&errout,"*") # 読み込み状況表示 # 単語を小文字変換しソートしたものを keyにして格納。 # 同一文字を含む単語は同じ keyに対応する valueに listの形式で格納。 # tableの key生成 # ↓文字列ソート s_word := csort(map(word)) # 小文字へ変換しソート # ↑小文字変換 例: "ACb" -> "abc" # 辞書 tableへ格納 put(\T_dic[s_word],word) | (T_dic[s_word] := [word]) # 格納例: key:"abc" -> value: ["ACb","Bca","cab"] } # end of while word .. close(dir) # 辞書ファイルクローズ write(&errout) write(" 終了:",&clock," ",n_line,"語ありました。") } # end of every n_pat .. write("\n",c_word," を、最大分割数 ",ndiv,"、最小文字長 ",nmin, " にて分割してチェック。開始:",&clock) # 辞書参照 n_comb := 0 # 組合せ数カウンタ n_find := 0 # 辞書にある件数カウンタ s_word := deletec(c_word,'.') # コマンドライン文字列から '.'を削除 n_dot := *c_word -*s_word # '.'の数 # ワイルドカード文字生成 ↓&lcaseは英小文字 ↓例: a-z,aa-zz,aaa-zzz every s_wild := mscomb(&lcase,n_dot) do { # ワイルドカード文字を、 s_check := s_wild || map(s_word) # コマンドライン引数の "."以外に足し、 # 分配文字数パターン取り出し every Lpat:= !L_lpat do { # Lpat例: [6]とか、[3,3]とか # 文字列分割結果取り出し Lword例: ["sunday"]とか,["day","sun"]とか every Lword := expcomb(s_check,Lpat) do { # 分配文字列を順次取り出して、 n_comb +:= 1 # チェック回数カウンタ＋１ if n_comb % 1000 = 0 then writes(&errout,"*") # チェック状況表示 # 辞書参照して、分配結果が全て辞書にあれば、L_loutにセット L_lout := tbl_ref(T_dic,Lword) | &null # 分配文字列が全て辞書にあれば、 # 辞書参照結果をセット。いずれかが辞書になければ、&nullでクリア。 # L_lout例: [["Day"],["day"],["Sun","sun","nus"]] # 分配文字列が全て辞書にあれば、書き出し if \L_lout then { # L_outに値がセットされていれば n_find +:= 1 # カウンタ＋１ writes(&errout,"!") # 合致表示 # "."を除く元の文字書き出し writes(s_word) # if *s_wild >= 1 then writes(" + ",s_wild) # ワイルドカード文字 writes(" ->") # # 辞書検索結果（２重 list）の書き出し every Lout := L_lout[i := 1 to *L_lout] do { # 参照結果を取り出して if i > 1 then writes(" +") # 先頭でなければ、区切りマーク every writes(" ",!Lout) # 参照結果を書き出し } # end of Lout .. write() } # end of if \L_lout .. } # end of every Lword .. } # end of every Lpat .. } # end of s_word .. write(&errout) write(n_comb," 通りの組合せのうち、",n_find," 通りが辞書にありました。", " 終了:",&clock) end ################### # Tableを list要素で参照し、結果を list連結 ################### # arg [1]: table key: "abc" -> value: "ABC" # [2]: list 参照する要素の list 例:["abc","def",...] # value : list table参照結果を格納 例:["ABC","DEF",...] # Usage : L := tbl_ref(T,L) # listの 要素のいずれかが tableに存在しなければ、fail procedure tbl_ref(T,L) # L1 := [] # ↓ Lの全ての要素につき every x := !L do put(L1,\T[x]) | fail # 参照 tableになければ failさせる。 return L1 end # 条件が全て揃った場合だけ結果を返す（いずれかの条件が成立しなかった場合は、 # 全体を failさせる。）には、その部分を サブ procedureにすること。 -----$ DICREFP6.ICN ( lines:151 words:589 ) ----------------<cut here tbl_ref()は、今回作りましたので、この dicrefp6.icnに入れてありますが、汎用的 な procedureですので、共通ライブラリに移す予定です。 ちょっと長いですが、ライブラリから抜粋したファイルを付けます。 -----^ FILE_X.ICN ( date:03-08-29 time:23:17 ) -------------<cut here #################### # file操作関係 procedure #################### # file_x.icn Rev.1.1 2003/08/29 windy 風つかい H.S. # file_e.icn から抜粋。 # This file is in the public domain. link string_x # top_get,top_cut # f_name(file_name) # 拡張子を除くファイル名生成(小文字) # F_name(file_name) # 拡張子を除くファイル名生成(大文字) #################### # 拡張子を除くファイル名を生成 #################### # Usageの file名訂正漏れを 防ぐための作成 # f_name(),F_name() 1997/12/27 windy 大文字、小文字対応に分ける。 # f_name() 1997/08/15 windy exe_name() -> f_name() # exe_name() 1997/06/02 windy 風つかい H.S. # args : ファイル名 # value: string # Icon入門講座４ Icon回り道（４） procedure f_name(file_name) /file_name := &progname # defaultは、実行ファイル名 return map(top_get('.',top_cut('\\',file_name))) end procedure F_name(file_name) /file_name := &progname # defaultは、実行ファイル名 return map(top_get('.',top_cut('\\',file_name)),&lcase,&ucase) end -----$ FILE_X.ICN ( lines:31 words:91 ) --------------------<cut here -----^ NUMBER_X.ICN ( date:03-08-29 time:22:49 ) -----------<cut here #################### # 数字関係補助 procedure #################### # number_x.icn Rev1.1 2003/08/29 windy 風つかい H.S. # number_e.icnから抜粋 # This file is in the public domein. # n_divd(r,max) # 正整数の分割（降順のみ） genarator # n_divdf(r,ndiv,nmin) # 正整数の分割（降順、分割数・最小数制限）generator #################### # 正整数分割 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 ... # Iconミニ講座３ # (4) -> [4],[3,1],[2,2],[2,1,1],[1,1,1,1] 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 #################### # 正整数分割 generator（フィルター） #################### # 5=3+2 等に数字分割する。この procedureは n_divdを呼びフィルターを掛けている。 # 分割パターンが多すぎる時に、制限をかけるために使用。 # arg [1]: 分割する元の数 # [2]: 最大分割数 # [3]: 最小数 # value : list # Usage : every L := n_divdf(r,ndiv,nmin) do .. # Iconミニ講座４ # (4,2,2) -> [4],[2,2] 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 -----$ NUMBER_X.ICN ( lines:60 words:243 ) -----------------<cut here -----^ STRING_X.ICN ( date:03-08-29 time:23:18 ) -----------<cut here #################### # 文字列操作 procedure #################### # string_x.icn Rev.1.1 2003/09/29 windy 風つかい H.S. # string_e.icn から抜粋 # This file is in the public domain. link stringsx # BIPL csort # ssub(s1,s2) # 文字列の引き算 # top_cut(c,s) # 先頭削除（最長一致削除） # top_get(c,s) # 先頭切り出し（最短一致切り出し） # 組合せ関係 # exscomb(s,m) # 文字の組合せ生成（同一文字対応） generator # mscomb(s,m) # 文字の組合せ生成 nHm（重複取り出し） genarator # 順列・組合せ共通 # new_pos(s) # 文字位置生成 （同一文字対応用） generator # 組合せ分配 # pcomb(s,L) # 文字の組合せを 分配 generator # expcomb(s,L,s_ref) # 文字の組合せを 分配（同一文字 同一数）generator #################### # 文字列の引き算 #################### # arg [1]: string 被削除文字列 # [2]: string 削除文字列 # value : string 結果文字列 # 文字列 s1の先頭から、文字列 s2の文字を削除。１：１で削除。 # ("abcabc","abd") -> "cabc" s2にある文字で、s1に無い文字は無視される。 # Iconミニ講座９ procedure ssub(s1,s2) every c := !s2 do { # s2から１文字ずつ取り出して ss := "" # 上記文字を削除後の文字列の格納エリア s1 ? { # s1を走査対象として、 if ss ||:= tab(upto(c)) then { # 文字が見つかれば そこ迄の文字列を # ssに足し込み move(1) # １文字スキップ ss ||:= tab(0) # 残りの文字列を足し込み s1 := ss # s1更新 } } } return s1 end #################### # 文字列の 先頭から特定文字までの部分 を取り去る。最長部分を取り去る。 #################### # arg : cset # value : string # Usage : top_cut(c,s) # Icon入門講座２（５） procedure top_cut(c,s) /s := &subject # sの指定がなければ &subject /c := ' \t' # cの指定がなければ spaceか tab s ? { # sを走査対象とする。 while tab(upto(c)) do tab(many(c)) # cが見つかる限り、走査位置を # その文字の後に移動。 return tab(0) # 残りの文字列を返す。 } end #################### # 文字列の 先頭から特定文字までの部分 を得る。最短部分を得る。 #################### # arg : cset # value : string # Usage : top_get(c,s) # Icon入門講座２（５） procedure top_get(c,s) /s := &subject # sの指定がなければ &subject /c := ' \t' # cの指定がなければ spaceか tab s ? { # sを走査対象とする。 return tab(upto(c) | 0) # cまで走査位置を移動しその間の } # 文字列を返す。cがみつからなけ # れば、末尾まで返す。 end #################### # 組合せ関係 #################### #################### # 文字列の組合せ 同一文字指定を許す n文字列から m個を選ぶ組合せ generator #################### # stringの組み合わせ # n個から、m個を選ぶ。（同一文字指定対応） # arg: [1]: s: string # [2]: m: integer # value: string # Usage: every ss := exscomb(s,m) do ... # Icon入門講座３（１１）scomb()を同一文字指定対応に拡張。 Iconミニ講座９ # ("abca",3) -> "aab","aac","abc" procedure exscomb(s,m) initial { /m := *s # デフォルト nCn (n = m = *s) s := csort(s) # 文字列をソートする。(BIPL:strings.icn) } if m = 0 then return "" # mを文字数カウンターに使う。 # 0にになったら、再帰終了。 suspend s[i := new_pos(s)] || exscomb(s[i+1 : 0], m -1) #↑ １文字選ぶ ↑ ↑←前で選んだ文字以降 ↑指定文字数に # ｜ の文字列に対し同じ 文字列を抑え # ｜ 処理を行う。 るためのカウ # 文字列の連結 ンター end ############################# # 文字列の nHm n文字列から、重複して m個を選ぶ組合せ generator ############################# # n個から 重複して、m個を選ぶ。 # arg [1]: string # [2]: integer # value : string # Usage : every ss := mscomb(s,m) do .. # ("abc",2) -> "aa","ab","ac","bb","bc","cc" procedure mscomb(s,m) initial { /m := *s } if m =0 then return "" # 再帰終了 every i := 1 to *s do { # １～文字列長まで # ↓ i番目の文字を取り出して suspend s[i] || mscomb(s[i:0],m-1) } # ↑その文字以降の文字と組み合わせる。 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 #################### # 分配の組合せ（同一文字指定・同一文字数指定対応） #################### # arg [1]: string 分配する英文字列：分配パターンのトータルに合ってること。 # [2]: list 分配パターン（降順の list） # [3]: string 前の文字列（同一文字数指定の場合に降順を選ぶための参照用） # value : list 分割された文字列（降順の組合せのみ）（ listに格納） # Usage : every LL := expcomb(s,L) do .. # ("abc", [2,1]) -> ["ab","c"], ["ac","b"], ["bc","a"] # ("abcd",[2,2]) -> ["ab","cd"],["ac","bd"],["ad","bc"] # 分配パターン生成に、number_e.icnの n_div(),n_divd(),n_divdf()が使えるかも。 # Iconミニ講座９ procedure expcomb(s,L,s_ref) /s_ref := "" # 指定なければ、空文字 s := csort(s) # 文字列ソート if *L = 1 then { # パターン要素の最後で、 if L[1] = *s_ref then { # 前回と文字数が同じで、 if s << s_ref then return &fail # 辞書順で前なら、失敗させる。 } return [s] # ↑で、無ければ、文字列を返す。 } # いずれににしても、再帰終了。 # １文字の文字列指定ならば、後は、順に１文字ずつ listに入れるだけ if L[1] = 1 then { # １文字の文字列指定ならば、 # 後は、順に１文字ずつ listに入れるだけ return [s[1]] ||| expcomb(s[2:0], L[2:0]) } # ↑先頭文字 ↑残り文字列 ↑残りのリスト # ２文字以上の文字列指定ならば、 every ss := exscomb(s,L[1]) do { # 文字の組合せを作って if *ss = *s_ref then { # 前回と文字数が同じなら、 if ss << s_ref then return &fail # 降順で無ければ、失敗させる。 } # ↓参照用文字列 suspend [ss] ||| expcomb(ssub(s,ss),L[2:0],ss) } # ↑組合せ文字 ↑残り文字列 ↑残りのリスト end -----$ STRING_X.ICN ( lines:198 words:657 ) ----------------<cut here -----^ STRINGSX.ICN ( date:03-08-29 time:23:13 ) -----------<cut here #################### # 文字列操作 procedure BIPL(Icon基本ライブラリー)より #################### # stringsx.icn Rev.1.1 2003/08/29 windy 風つかい H.S. # BIPL strings.icn から抜粋 # This file is in the public domain. #################### # 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から !で要素を取り出す時には、アルファベット順に取り出せる。 #################### # strings.icnに含まれる 文字の削除 procedure #################### procedure deletec(s, c) #: delete characters local result # ローカル宣言（無くても良い） result := "" # 削除後の文字列格納エリア s ? { # sを走査対象として、 while result ||:= tab(upto(c)) do # cが見つかる迄の文字列を足し込んで tab(many(c)) # c以外の文字までスキップ return result ||:= tab(0) # 余りの文字を足し込む } end -----$ STRINGSX.ICN ( lines:32 words:117 ) -----------------<cut here 風つかい(hshinoh@mb.neweb.ne.jp) IconのWWWは、 http://www.cs.arizona.edu/icon/ UniconのWWWは、http://unicon.sourceforge.net/index.html BGM: Yesterday's Dream / 山見慶子 (2003/08/30 TSfreeB.txt) ■ TSfree > Iconミニ講座 あまり（procedure構成） 風つかい ライブラリ整理の際、ちょっと遊んでみましたので、ご参考に。 テーブルをリストの要素で参照する procedureの３つの例です。 -----^ PROC01.ICN ( date:03-08-29 time:23:38 ) -------------<cut here #################### # テーブル参照プログラム例 #################### # proc01.icn Rev.1.1 2003/08/29 windy 風つかい H.S. # TS Network TSfree # This file is in the public domain. procedure main() T := table() # table生成 T["a"] := "AA" ; T["b"] := "BB" ; T["c"] := "CC" # データ登録 # ↓データ１ # ↓データ２ L := [["a","b","c"],["a","d","c"]] # テストデータ # procedure のテスト procedureを引数にして、procedureを呼ぶ。 test(tbl_ref1,T,L) test(tbl_ref2,T,L) test(tbl_ref3,T,L) end # procedureのテスト # arg [1]: procedure # [2]: table テスト用 table # [3]: list テスト用 list procedure test(prcdr,T,L) write(image(prcdr)) # procedure名 every L1 := !L do { # テスト用 listからデータを取り出して every writes(" ",!L1) # 書き出し writes(" -> ") L2 := prcdr(T,L1) | ["error"] # 処理結果 every writes(" ",!L2) # 処理結果書き出し write() } write("----- ----- -----") # 仕切線 end ################### # Table参照し、結果を list連結 ################### # arg [1]: table key -> value # [2]: list 参照する要素の list 例:["abc","def",...] # value : list table参照結果を格納 例:["ABC","DEF",...] # Usage : L := tbl_ref(T,L) # args[2]の 要素のいずれかが tableに存在しなければ、fail # 条件が全て揃った場合だけ結果を返す（いずれかの条件が成立しなかった場合は、 # 全体を failさせる。）には、その部分を procedureにすること。 # 再帰 procedure tbl_ref1(T,L) # ↓ \xは存在すればその値、なければ fail return if *L = 1 then [ \T[ L[1] ] ] #←listの最後なら再帰終了 else [ \T[ L[1] ] ] ||| tbl_ref1(T,L[2:0]) end # listの連結 ↑ ↑最後でなければ、再帰 # every procedure tbl_ref2(T,L) # <- この辺が分かりやすいかな。 L1 := [] every x := !L do put(L1,\T[x]) | fail # いずれか辞書になければ、fail return L1 end # whileループ procedure tbl_ref3(T,L) L1 := [] while x := get(L) do put(L1,\T[x]) | fail # いずれか辞書になければ、fail return L1 end -----$ PROC01.ICN ( lines:65 words:234 ) -------------------<cut here 動かすとこんな風です。 -----^ PROC01 ( date:03-08-29 time:23:38 ) -----------------<cut here procedure tbl_ref1 a b c -> AA BB CC a d c -> error ----- ----- ----- procedure tbl_ref2 a b c -> AA BB CC a d c -> error ----- ----- ----- procedure tbl_ref3 a b c -> AA BB CC a d c -> error ----- ----- ----- -----$ PROC01 ( lines:12 words:51 ) ------------------------<cut here 風つかい(hshinoh@mb.neweb.ne.jp) IconのWWWは、 http://www.cs.arizona.edu/icon/ UniconのWWWは、http://unicon.sourceforge.net/index.html BGM: for Masqurade / 山見慶子 (2003/08/30 TSfreeC.txt)