パタンマッチャをGenerate and Filter で利用
展開ヘルプでは、時刻指定の状態遷移機械.iconを幅優先的に状態遷移機械をたどって木構造を生成.iconのように木構造に展開するのと同時に、ユーザから与えられた検索文字列とそれまでに生成された文字列とのマッチングを行なってシフタアルゴリズムのマッチング状況を木のノードに格納する。 ユーザから「時計 3 時」☆という検索パタンが与えられたときは「時計 3 時」のパタンマッチャ.iconのような状態遷移機械を利用する。
この状態遷移機械の初期状態での各ノードのアクティブ状態は初期状態のアクティブ状態.iconになる。シフタアルゴリズムによる表現では{00100, 01000, 10000}となるので、この値を開始ノードS に格納しておく。
この状態遷移機械が「時」を認識すると、S に格納された値と入力文字「時」からマッチング状態が計算されてアクティブ状態が「時」を認識した後の状態.iconに変化し、この値 {01110, 11100, 11000}を 2 番目のノードに格納する。
このように、各ノードのマッチング状態は遷移前のノードの状態と遷移文字のみから計算されてノードに保存される。状態遷移機械を木構造に展開して文字列を生成するのと同時にシフタアルゴリズムのマッチングを実行し、その結果のマッチングパタンを出力される木構造のノードに格納することにより、文字列の出力とフィルタリングを同時に行なうGenerate and Filterが実現されることになる。 「時計 3 時」のパタンマッチャ.iconに対して「時計 3 時」というパタンが与えられたときのGenerate and Filter実行により作成される木構造を「時計 3時」へのマッチ状態を計算しながら木を生成.iconに示す。 「時計 3時」へのマッチ状態を計算しながら木を生成.icon
ノード1 のマッチ状態を見るとシフタアルゴリズムのマッチャの右上のノードがアクティブになっているため、「時間を3」および「時刻を3」という文字列が「時計 3 時」というパタンに曖昧度2 でマッチしていることがわかる。また2 では最右桁の上から二番目のノードもアクティブになっているため、「時間を3 時」および「時刻を3 時」という文字列が「時計 3 時」に曖昧度1 でマッチしていることがわかる。