Tcl拡張 – hashtrie

一括置換やLongest Common Prefix Searchなどを行うためのtrie風データ構造です。
今のところ、渡されるtrieの中身などはチェックしていません。そのうち直します。
拡張名：hashtrie
ダウンロード：hashtrie.zip
使い方は下記参照：

% package require hashtrie
1.0
% set trie [hashtrie::new]
{} {} 0 {}
% set trie [hashtrie::add $trie test テスト]
{t-0 1 e-1 2 s-2 3 t-3 4} {4 テスト} 4 {4 test}
% set trie [hashtrie::add $trie check チェック]
{t-0 1 e-1 2 s-2 3 t-3 4 c-0 5 h-5 6 e-6 7 c-7 8 k-8 9} {4 テスト 9 チェック} 9 {4 test 9 check}
% set d [dict create 今日 きょう 明日 あした 明後日 あさって]
今日 きょう 明日 あした 明後日 あさって
% set trie [hashtrie::import $trie $d]
{t-0 1 e-1 2 s-2 3 t-3 4 c-0 5 h-5 6 e-6 7 c-7 8 k-8 9 今-0 10 日-10 11 明-0 12 日-12 13 後-12 14 日-14 15} {4 テスト 9 チェック 11 きょう 13 あした 15 あさって} 15 {4 test 9 check 11 今日 13 明日 15 明後日}
% hashtrie::exists $trie 今日
1
% hashtrie::replace $trie "今日と明日はtestで忙しい。"
きょうとあしたはテストで忙しい。
% hashtrie::remove trie check
1
% puts $trie
{t-0 1 e-1 2 s-2 3 t-3 4 c-0 5 h-5 6 e-6 7 c-7 8 k-8 9 今-0 10 日-10 11 明-0 12 日-12 13 後-12 14 日-14 15} {4 テスト 11 きょう 13 あした 15 あさって} 15 {4 test 11 今日 13 明日 15 明後日}

DESCRIPTION

hashtrie::new {}

空のhashtrieを作ります。上の例のように、hashtrieは3つのdictと1つの数字で構成されるリストです。

hashtrie::add {trie word value}

hashtrieにデータを登録します。wordとそれに対応する値であるvalueを登録します。

hashtrie::remove {trieName word}

hashtrieからwordに対応するデータを削除します。成功すれば1、失敗すれば0を返します。引数のtrieNameには値ではなく、変数の名前を渡します。

hashtrie::exists {trie word}

trieにwordが含まれていれば1、含まれていなければ0が返ってきます。

hashtrie::commonprefix {trie str}

strの先頭から検索を行い、trieに含まれている単語が含まれていれば、その単語に対応するstateと単語の終端位置のペアをリストにして返します。検索で何もヒットしなかった場合は何も返しません。なお、後述のhashtrie::getvalueやhashtrie::getoriginalを利用すれば、返り値のstateに対応する単語のデータを得ることができます。

% set trie [hashtrie::import $trie [dict create 国 kuni 国家 kokka 国家警察 kokkakeisatsu 国家機関 kokkakikan]]
{国-0 1 家-1 2 警-2 3 察-3 4 機-2 5 関-5 6} {1 kuni 2 kokka 4 kokkakeisatsu 6 kokkakikan} 6 {1 国 2 国家 4 国家警察 6 国家機関}
% hashtrie::commonprefix $trie 国家機関と舞踏会
{1 0} {2 1} {6 3}

hashtrie::longest {trie str}

commonprefixと同様の検索を行い、最も長い単語のstateと終端位置を返します。

hashtrie::getall {trie str}

strの終端まで検索を行い、trieに含まれている単語が存在すれば、その単語に対応するstateと単語の終端位置のペアをリストにして返します（先頭からの最長一致で検索を行うため、すべての単語にヒットするわけではありません）。

hashtrie::getvalue {trie state}

stateに対応する置換候補を返します。

% set trie [hashtrie::import $trie [dict create 国 kuni 国家 kokka 国家警察 kokkakeisatsu 国家機関 kokkakikan]]
{国-0 1 家-1 2 警-2 3 察-3 4 機-2 5 関-5 6} {1 kuni 2 kokka 4 kokkakeisatsu 6 kokkakikan} 6 {1 国 2 国家 4 国家警察 6 国家機関}
% hashtrie::commonprefix $trie 国家機関と舞踏会
{1 0} {2 1} {6 3}
% hashtrie::getvalue $trie 6
kokkakikan

hashtrie::getoriginal {trie state}

stateに対応する単語を返します。

% set trie [hashtrie::import $trie [dict create 国 kuni 国家 kokka 国家警察 kokkakeisatsu 国家機関 kokkakikan]]
{国-0 1 家-1 2 警-2 3 察-3 4 機-2 5 関-5 6} {1 kuni 2 kokka 4 kokkakeisatsu 6 kokkakikan} 6 {1 国 2 国家 4 国家警察 6 国家機関}
% hashtrie::commonprefix $trie 国家機関と舞踏会
{1 0} {2 1} {6 3}
% hashtrie::getoriginal $trie 6
国家機関

hashtrie::replace {trie str ?mode? ?template? ?min?}

strを走査し、trieに含まれている単語があれば、その最も長い単語を対応する値に置換します。返り値は置換後の文字列です。

% set trie [hashtrie::import $trie [dict create 国 kuni 国家 kokka 国家警察 kokkakeisatsu 国家機関 kokkakikan]]
{国-0 1 家-1 2 警-2 3 察-3 4 機-2 5 関-5 6} {1 kuni 2 kokka 4 kokkakeisatsu 6 kokkakikan} 6 {1 国 2 国家 4 国家警察 6 国家機関}
% hashtrie::replace $trie 国家機関と舞踏会
kokkakikanと舞踏会

hashtrie::import {trie dict ?mode? ?widget?}

trieにdictからまとめてデータを登録します。dictにはTclのdictを渡します。modeでデータが重複していた場合の処理方法を指定します。ignore、merge、updateの3つのモードを選択することができ、ignoreは重複データを無視して登録しない、mergeは既存のデータをリストと見なし、新たなデータとマージして重複のないリストを登録する、updateは重複データを上書きするかたちとなります。デフォルトはupdateです。widgetには登録の進捗状況（dictの何件目の要素を処理しているか）を表示するための変数を指定します。たとえばlabelウィジェットの-textvariableの変数を指定します。

% set trie [hashtrie::import $trie [dict create 国 kuni 国家 kokka 国家警察 kokkakeisatsu 国家機関 kokkakikan]]
{国-0 1 家-1 2 警-2 3 察-3 4 機-2 5 関-5 6} {1 kuni 2 kokka 4 kokkakeisatsu 6 kokkakikan} 6 {1 国 2 国家 4 国家警察 6 国家機関}

hashtrie::export {trie ?mark?}

trieに含まれている単語と値のペアをdictにして返します。

% hashtrie::export $trie
国 kuni 国家 kokka 国家警察 kokkakeisatsu 国家機関 kokkakikan

hashtrie::save {trie filename ?encode? ?newline?}

trieをファイルに保存します。文字コードと改行コードを指定することができます。成功すると1が返ってきます。

hashtrie::load {filename ?encode? ?newline?}

ファイルに保存したtrieを読み込みます。saveと同様、文字コードと改行コードを指定することができます。返り値はtrieのデータです。