自分向けの npm ライブラリ @monyone/aho-corasick を作ってます。
ただ、実用するにあたって、AC法で最左最長マッチをどう求めるのか悩みました。
よく言われる、結果をソートするのは怠い...
ランダムケースでテストするとマッチ数がボトルネックになるし...
じゃあ、作ってしまうかということで作ってみた。
構築時の計算量は従来のAC法そのまま、償却O(N)の最左最長マッチをするAC法を。
やったこと
結局のところ、こういう PMA を作ってしまえばよかった。
- Trie に持つマッチは最長である1つだけ持つようにする
- キーワードの node の場合はそのキーワードのマッチ
- そうでないなら、failure link から得たマッチ
- Failure Link 構築を最左最長マッチ向けにする
- キーワードに対応する node の Failure Link は root にする
- それ以外のノードは通常通りのやり方で伝播する
- サーチ時に特殊なことをしてマッチをまとめる
このようにすることで、各ノードでの最長マッチがノードに保持される。
しかも、このマッチの数はノード当たり1つなので、全体でN個になる。
じゃあ、サーチ時に特殊なことをするって何か、をこれ以下に書く
最左最長マッチ (空間計算量: O(N))
簡単なのは、N文字のテキストに対して、N要素の開始位置をキーとした配列を作る方法だ。
例えば、以下のような配列を用意する。
const text = '入力の文字列が与えられるとする';
type Match = { begin: number, end: number, keyword: string };
const candidates: (Match | null)[] = Array.from({ length: text.length }, () => null);
マッチを見つけたら、マッチの開始位置をキーとして配列を上書きする。
マッチの数はgoto遷移の数しかないので、これは合計でO(N)になる。
上書きして良いのは、終了位置が必ず伸びていく性質上、必ず採用すべきだから。
Failure遷移については、いじる前と同じなので全体でみると償却O(N)になる。
for (let i = 0; i < text.length; i++) {
const ch = text[i];
while (!state.can(ch) && state !== this.root) {
state = this.failure_link.get(state)!;
}
state = state.go(ch) ?? this.root;
if (!state.empty()) {
const keyword = state.value()!;
const begin = i - keyword.length + 1;
candidates[begin] = { begin, end: i + 1, keyword };
}
}
そのようにして作った配列から、オーバーラップしないように抜き出せば終わり。
例えば、このような形になるだろう。
const result: Match[] = [];
for (let i = 0; i < text.length; ) {
const candidate = candidates[i]
if (candidate == null) { i++; continue; }
result.push(candidate);
i = candidate.end;
}
return result;
最左最長マッチ (空間計算量: O(マッチ数))
実は、マッチをスタックで保持することで、償却テクが適用で
きる。
なぜなら、範囲の右端が単調増加なので、消す操作は右側から順に判断すればいいから。
しかも、スタック構成なら1-passになる。
このような感じでスタックを操作して、オーバーラップしない区間にする。
const keyword = state.value()!;
const length = keyword.length;
const begin = i - length + 1;
const end = i + 1;
while (true) {
if (candidates.length === 0) {
candidates.push({ begin, end, keyword })
break;
}
const stack = candidates.length - 1;
if (candidates[candidates.length - 1].end <= begin) {
candidates.push({ begin, end, keyword });
break;
} else if (begin > candidates[stack].begin) {
break;
} else {
candidates.pop();
}
}
コード
最左最長マッチ (空間計算量: O(N))
class Trie {
public readonly parent: Trie | null = null;
private goto: Map<string, Trie> = new Map<string, Trie>();
private keyword: string | null = null;
public constructor(parent?: Trie) {
this.parent = parent ?? null;
}
public can(s: string) {
return this.goto.has(s);
}
public go(s: string) {
return this.goto.get(s);
}
public define(s: string, next: Trie) {
return this.goto.set(s, next);
}
public undef(s: string) {
this.goto.delete(s);
}
public entries() {
return this.goto.entries();
}
public empty() {
return this.keyword == null;
}
public add(k: string) {
this.keyword = k;
}
public delete(k: string) {
this.keyword = null;
}
public value() {
return this.keyword;
}
public merge(t?: Trie) {
this.keyword ??= t?.keyword ?? null;
}
}
export class AhoCorasick {
protected root = new Trie();
protected failure_link = new Map<Trie, Trie>();
constructor(keywords: string[]) {
// build goto
for (const keyword of keywords) {
let current: Trie = this.root;
for (let i = 0; i < keyword.length; i++) {
const ch = keyword[i];
let next = current.go(ch) ?? (new Trie(current))
current.define(ch, next);
current = next;
}
current.add(keyword);
}
// build failure
const queue: [Trie, string][] = [];
for (const [ch, next] of this.root.entries()) {
queue.push([next, ch]);
}
while (queue.length > 0) {
const [current, ch] = queue.shift()!;
const parent = current.parent!;
if (current.empty()) { // calc failure
let failure = this.failure_link.get(parent) ?? null;
while (failure != null && !failure.can(ch)) {
failure = this.failure_link.get(failure) ?? null;
}
failure = failure?.go(ch) ?? this.root;
this.failure_link.set(current, failure);
current.merge(failure);
} else { // if keyword, immidiate root
this.failure_link.set(current, this.root);
}
for (const [ch, next] of current.entries()) {
queue.push([next, ch]);
}
}
}
public matchInText(text: string): { begin: number, end: number, keyword: string }[] {
const result: { begin: number, end: number, keyword: string }[] = [];
let state: Trie = this.root;
const candidates: ({ begin: number, end: number, keyword: string } | null)[] = Array.from({ length: text.length }, () => null);
for (let i = 0; i < text.length; i++) {
const ch = text[i];
while (!state.can(ch) && state !== this.root) {
state = this.failure_link.get(state)!;
}
state = state.go(ch) ?? this.root;
if (!state.empty()) {
const keyword = state.value()!;
const begin = i - keyword.length + 1;
candidates[begin] = { begin, end: i + 1, keyword };
}
}
for (let i = 0; i < text.length; ) {
const candidate = candidates[i]
if (candidate == null) { i++; continue; }
result.push(candidate);
i = candidate.end;
}
return result;
}
}
最左最長マッチ (空間計算量: O(マッチ数))
class Trie {
public readonly parent: Trie | null = null;
private keyword: string | null = null;
private goto: Map<string, Trie> = new Map<string, Trie>();
public constructor(parent?: Trie) {
this.parent = parent ?? null;
}
public can(s: string) {
return this.goto.has(s);
}
public go(s: string) {
return this.goto.get(s);
}
public define(s: string, next: Trie) {
return this.goto.set(s, next);
}
public undef(s: string) {
this.goto.delete(s);
}
public entries() {
return this.goto.entries();
}
public empty() {
return this.keyword == null;
}
public add(k: string) {
this.keyword = k;
}
public delete(k: string) {
this.keyword = null;
}
public value() {
return this.keyword;
}
public merge(t?: Trie) {
this.keyword ??= t?.keyword ?? null;
}
}
export class AhoCorasick {
protected root = new Trie();
protected failure_link = new Map<Trie, Trie>();
constructor(keywords: string[]) {
// build goto
for (const keyword of keywords) {
let current = this.root;
for (let i = 0; i < keyword.length; i++) {
const ch = keyword[i];
let next = current.go(ch) ?? (new Trie(current))
current.define(ch, next);
current = next;
}
current.add(keyword);
}
// build failure
{
const queue: [Trie, string][] = [];
for (const [ch, next] of this.root.entries()) {
queue.push([next, ch]);
}
while (queue.length > 0) {
const data = queue.shift()!;
const current = data[0];
const ch = data[1];
const parent = current.parent!;
// calc failure
if (current.empty()) {
let failure = this.failure_link.get(parent) ?? null;
while (failure != null && !failure.can(ch)) {
failure = this.failure_link.get(failure) ?? null;
}
failure = failure?.go(ch) ?? this.root;
this.failure_link.set(current, failure);
current.merge(failure);
} else {
this.failure_link.set(current, this.root);
}
for (const [ch, next] of current.entries()) {
queue.push([next, ch]);
}
}
}
}
public matchInText(text: string): { begin: number, end: number, keyword: string }[] {
const candidates: { begin: number, end: number, keyword: string }[] = [];
let state: Trie = this.root;
for (let i = 0; i < text.length; i++) {
const ch = text[i];
if (!state.can(ch)) { // use failure
while (state !== this.root && !(state.can(ch))) {
state = this.failure_link.get(state)!;
}
}
state = state.go(ch) ?? this.root;
if (!state.empty()) {
const keyword = state.value()!;
const length = keyword.length;
const begin = i - length + 1;
const end = i + 1;
while (true) {
if (candidates.length === 0) {
candidates.push({ begin, end, keyword })
break;
}
const stack = candidates.length - 1;
if (candidates[candidates.length - 1].end <= begin) {
candidates.push({ begin, end, keyword });
break;
} else if (begin > candidates[stack].begin) {
break;
} else {
candidates.pop();
}
}
}
}
return candidates;
}
}
使いどころ
競技プログラミング的な需要はあるかもしれない。
通常のマッチ数が N^2 に近くなるケースでも、こちらは全体で償却O(N)となるので。
実際の需要は微妙だが、ライブラリとしてはソートする手間を減らせてよかった。
備考
Rust の aho-corasick クレートとはちょっとやり方が違うみたい...
読み解くのが難しいので、そのうち読んでみます。
あと、動的Aho-Corasickも提供してるので、みてみてねー