Bitap Algorithmを理解する (using asearch)

用語を決めておきたい

「ビットパターン」だの「変数」だの「状態」だのを適当に使ったため、どれがどれを示しているのかよくわからなくなってきた

各種初期値の定義

32bit目だけを立てたビットパターン

code:mod.ts

const INITPAT = 0x80000000;

code:mod.ts

const MAXCHAR = 0x10000;

大文字小文字変換

code:mod.ts

const isupper = (c: number) => (c >= 0x41) && (c <= 0x5a);

const islower = (c: number) => (c >= 0x61) && (c <= 0x7a);

const tolower = (c: number) => isupper(c) ? (c + 0x20) : c;

const toupper = (c: number) => islower(c) ? (c - 0x20) : c;

各種初期値の定義その2

code:mod.ts

const wildCard = 0x20;

code:mod.ts

export function Asearch(source: string) {

前処理

遷移可能な場所を記録する

表現方法

それぞれの文字に対応するビットパターン

bitが立っている場所でそれらの文字が来ることを表す

ここで使用するビットパターンの最大ビット長で、検索可能な最大文字数が決まる

全ての文字に対応するために、任意の文字コードからビットパターンに写す写像を作成する必要がある

本実装では予め全ての文字コードごとにビットパターンを用意している

これは検索に使わない文字のビットパターンも用意しなければならないので、かなりメモリ効率が悪いと思われる

もちろんベンチマークをとって実際に速くなったかどうかを調べる

code:mod.ts

const shiftpat = new Float64Array(MAXCHAR);

let epsilon = 0;

code:mod.ts

let mask = INITPAT;

for (const i of unpack(source)) {

if (i === wildCard) {

code:mod.ts

epsilon |= mask;

} else {

文字の場所をビットパターンに記録する

ここをいじれば、いろんな同一視方法を組み込める

e.g.

ひらがなカタカナ無視

全角半角無視

見た目が似ている文字の違いを無視

今回の場合は1本しか立っていないが

code:mod.ts

mask >>>= 1;

}

}

code:mod.ts

const acceptpat = mask;

それ以上は全ての変数が未受理になるので計測できない

もちろんその分計算量が増える

code:mod.ts

function getState(str = "") {

NFAの初期化

code:initial_state

i3 0000 0000 0000 0000 0000 0000 0000 0000

i2 0000 0000 0000 0000 0000 0000 0000 0000

i1 0000 0000 0000 0000 0000 0000 0000 0000

i0 1000 0000 0000 0000 0000 0000 0000 0000

code:mod.ts

被検索文字列の全ての文字に対して機械を動かしている

変数のどれかが受理状態になった時点で遷移を打ち切っていいのでは

ビット演算の意味を考える

i0 = (i0 & epsilon) | ((i0 & mask) >>> 1)

1つ下の状態を上の状態に転写している

適当な短い文字で試してみるか

wild cardありとwild cardなしとで試したい

ちょっとわかった

例：

これが文字を受理して状態遷移したということ

code:mod.ts

for (const c of unpack(str)) {

i3 = (i3 & epsilon) | ((i3 & mask) >>> 1) | (i2 >>> 1) | i2;

i2 = (i2 & epsilon) | ((i2 & mask) >>> 1) | (i1 >>> 1) | i1;

i1 = (i1 & epsilon) | ((i1 & mask) >>> 1) | (i0 >>> 1) | i0;

i0 = (i0 & epsilon) | ((i0 & mask) >>> 1);

i1 |= (i0 >>> 1);

i2 |= (i1 >>> 1);

i3 |= (i2 >>> 1);

}

}

一致判定を行う函数

code:mod.ts

function test(str: string, distance = 0) {

const state = getState(str);

distance = Math.min(INITSTATE.length - 1, distance);

}

検索文字列とどのくらい一致したかがわかるので、検索結果の並び替えに使える

code:mod.ts

function match(str: string) {

const state = getState(str);

return { found: false };

}

const distance = state.findIndex((i) => (i & acceptpat) !== 0);

return { found: true, distance };

}

code:mod.ts

return {

test,

match,

source,

};

}

code:mod.ts

function* unpack(str: string) {

for (const char of str) {

yield char.charCodeAt(0);

}

}