作者: Hiroshi Shinohara
日時: 2003/8/23(11:24)
Iconミニ講座6(辞書参照の別方式)

 前回で、ミニ講座は終わったつもりでいたのですが、辞書参照がどうもスッキリ
しませんので、ツラツラ考えていました。(シツコイ!)

 特定文字を使った単語をスバヤク検索するのだったら、
  ・特定文字を使った文字をまとめてテーブルに登録しておけば、
   スバヤク検索できる。 ということで、
  ・辞書の単語の文字列をソートしたもので、インデックスを作っておいて、
   同一文字を使用した単語をまとめて、テーブルに登録しておき、
  ・検索文字列をソートして、テーブルを参照すれば、
  ・一回の参照で、候補の単語群が見つかる。
 と、気が付きました。

 例えば、"abcd"と "cdab"と "dcab"という単語があったとして、皆ソートすると、
 "abcd"となります。 ソートした "abcd"を インデックス(Iconでは keyと言い
ます。)として、値に ["abcd","cdab","dcab"]と格納しておけば、"abcd"で参照
すれば、文字の配列を変換した場合の候補が、一挙に出てきます。
 この方式ですと、不明文字を、1〜2文字入れて 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 {           # 辞書を1行ずつ読み込んで、
    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 とすると、こういう結果になります。 辞書読込の際に、加工を
していますので、読込時間が 42秒に増えています。
-----^ 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@...)
IconのWWWは、  http://www.cs.arizona.edu/icon/
UniconのWWWは、http://unicon.sourceforge.net/index.html
BGM: Battery's not included / 森山威男&杉本喜代志