Myersのbit-parallel法

algorithmに手を加えれば、もしかしたら実装できるかも

algorithmの解説

元論文が図解付きで詳しい

擬似コードではない、具体的な実装が紹介されている記事は以下の通り

わかりやすい

code:mod.ts

/** 検索函数 */

export interface Filter {

/** 与えた文字列に一致する編集距離のリストを計算する

*

* @param text 被検索文字列

* @return i番目に、textのi番目の近似文字列出現の編集距離を格納した配列

*/

(text: string): number[];

}

/** あいまい検索する

*

* @param query 検索文字列

* @return 検索用函数

*/

export const makeFilter = (query: string): Filter => {

// 末尾が最初の文字のビットを表す

const Peq = new Map<string, number>();

{

let i = 1;

for (const q of rquery) {

Peq.set(q, (Peq.get(q) ?? 0) | i);

const pil = q.toLowerCase();

Peq.set(pil, (Peq.get(pil) ?? 0) | i);

const piu = q.toUpperCase();

Peq.set(piu, (Peq.get(piu) ?? 0) | i);

i <<= 1;

}

}

const m = rquery.length; //文字列数

const Pv0 = ~(~(0) << m); // 右側からm個のbitsが立ったビット列

const accept = 1 << (m - 1);

return (text: string): number[] => {

let Mv = 0;

let Pv = Pv0;

const Cm: number[] = [];

let j = rtext.length;

for (const t of rtext) {

const Eq = Peq.get(t) ?? 0;

const Xv = Eq | Mv;

const Xh = (((Eq & Pv) + Pv) ^ Pv) | Eq;

const Ph = Mv | ~(Xh | Pv);

const Mh = Pv & Xh;

Pv = (Mh << 1) | ~(Xv | (Ph << 1));

Mv = (Ph << 1) & Xv;

j--;

}

return Cm;

};

};

scrapbox.Project.pagesから検索する

検索速度

query長によらず、100,000件でだいたい100~200ms

45,000件だと70~100ms

5,000件だと10~50ms

5,000件ずつ検索すれば、UIをブロックせずにすみそう

並び替えまで対応すると、

code:test.js

import { makeFilter } from "./mod.ts";

const getMaxDistance = [

0, // 空文字のとき

0, 0,

1, 1,

2, 2, 2, 2,

3, 3, 3, 3, 3, 3,

4, 4, 4, 4, 4, 4, 4, 4, 4, 4,

5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,

6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,

];

window.search = (p, l) => {

const pages = scrapbox.Project.pages.slice(0, l); // 生成にやや時間がかかるので、計測範囲から外す

if (p.trim() === "") return [];

console.time(tag);

const filter = makeFilter(p);

const result = pages.flatMap(({ title, titleLc, updated }) => {

const { dist, pos } = filter(titleLc).reduce((prev, dist, i) => {

if(prev.dist <= dist)return prev;

prev.dist = dist;

prev.pos = i;

return prev;

}, { dist: m, pos: 0 });

})

.sort((a, b) => {

const ldiff = a.dist - b.dist;

if (ldiff !== 0) return ldiff;

const pdiff = a.pos - b.pos;

if (pdiff !== 0) return pdiff;

const udiff = b.updated - a.updated;

if (udiff !== 0) return udiff;

return a.title.length - b.title.length;

});

console.timeEnd(tag);

return result;

};

並び替え対応

並び替えなしより若干遅くなる

code:permutation.js

import { makeFilter } from "./mod.ts";

const getMaxDistance = [

0, // 空文字のとき

0, 0,

1, 1,

2, 2, 2, 2,

3, 3, 3, 3, 3, 3,

4, 4, 4, 4, 4, 4, 4, 4, 4, 4,

5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,

6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,

];

const filter = (m, max, filter_, pages) => pages.flatMap(

({ title, updated, dist, matches }) => {

matches ??= [];

dist ??= 0;

const result = filter_(title)

// 別のqueryでマッチした箇所は除く

.flatMap((d, i) =>

[]

);

if (result.length === 0) return [];

if(prev.dist <= dist) return prev;

prev.dist = dist;

prev.start = i;

prev.end = i + m -1;

return prev;

}, { dist: m, start: 0, end: m - 1 });

const newDist = newMatch.dist + dist;

if (newDist > max) return [];

}

);

const sorter = (a, b) => {

const ldiff = a.dist - b.dist;

if (ldiff !== 0) return ldiff;

// マッチ位置が早い順に並べる

for (let i = 0; i < sa.length; i++) {

if (sdiff !== 0) return sdiff;

}

const udiff = b.updated - a.updated;

if (udiff !== 0) return udiff;

return a.title.length - b.title.length;

};

window.search = (p, l) => {

const pages = scrapbox.Project.pages.slice(0, l); // 生成にやや時間がかかるので、計測範囲から外す

/** キーワードリスト

*

* - 空白は取り除く

* - 長い順に並び替えておく

* - 長いqueryから検索したほうが、少なく絞り込める

*/

const queries = p.trim().replaceAll("_", " ").split(/\s+/)

.sort((a, b) => b.length -a.length);

if (queries.length === 0 || queries.every((q) => q === "")) return [];

console.time(tag);

let result = pages;

for (const query of queries) {

result = filter(m, max, makeFilter(query), result);

}

result.sort(sorter)

console.timeEnd(tag);

return result;

};