fizzSearch
あいまい検索クラス
ambiguous text search
cf.
これを
に書き直しただけ
課題
検索を途中で打ち切る
最大n件しか使わないなら、それ以上検索する必要がない
高速化を期待できる
並列で検索している場合も使える
個々のworkerごとに検索数上限を設定するのは計算が難しいが、代わりに最終的な検索数上限をつかえばいい
2020-11-19 08:37:14 やってみた
検索語句に最も関連している順に並び替えしたい
対策
類似度を数値化し、それを元に並べ替える
2020-10-15 15:27:34 ambig
の順番に検索結果を並べ替える
完全一致、一文字間違い、2文字間違い、……と並べることができる
もうちょっと高速化したい
検索対象の前後に空白を入れることで解決した
ひらがな/カタカナ/カタカナを区別しないで検索できるようにしたい
検索候補と、検索文字列とを全てひらがな/alphabetに変換してから検索を開始する
Asearchに渡す前に変換すればいいかな?
あまり負荷がかかるようであれば、予め利用者側で変換済みの文字列を用意してもらうという手もある
更新とか
2021-02-04 18:37:01 Asearch
を少しrefactoringした
2020-11-02 10:38:03
検索keyword or 検索候補がからのときは、0件の検索結果を返すようにした
検索keywordに空白を与えると固まる問題への対処
2020-10-15 15:38:33
あいまい度順に検索結果が並ぶようにした
2020-10-12 01:48:50
func
を引数に追加
ambig
の上限値が3になっていたのを4に直した
limitCount <= 4
2020-09-17 20:34:24
asearchで部分一致検索する方法がわかったので、歯抜けマッチングを使う必要がなくなった
2020-09-17 11:30:57
script.jsclass Asearch {
get INITPAT() {return 0x80000000;} // 0100,0000,0000,0000,0000,0000,0000,0000
get MAXCHAR() {return 0x100;}
get INITSTATE() {return [this.INITPAT, 0, 0, 0];}
constructor(source) {
this.source = source;
this.shiftpat = Array(this.MAXCHAR).map(_ => 0);
this.epsilon = 0;
let mask = this.INITPAT;
const ref = this.unpack(this.source);
for (const item of ref) {
// 0x20 is a space
if (item === 0x20) {
this.epsilon |= mask;
} else {
this.shiftpat[item] |= mask;
this.shiftpat[this.toupper(item)] |= mask;
this.shiftpat[this.tolower(item)] |= mask;
mask >>>= 1;
}
}
this.acceptpat = mask;
}
isupper(c) {
// 0x41 = A, 0x5a = Z
return (c >= 0x41) && (c <= 0x5a);
}
islower(c) {
// 0x61 = a, 0x7a = z
return (c >= 0x61) && (c <= 0x7a);
}
tolower(c) {
return this.isupper(c) ? c + 0x20 : c;
}
toupper(c) {
return this.islower(c) ? c - 0x20 : c;
}
state(str = '') {
let i0 = this.INITSTATE[0];
let i1 = this.INITSTATE[1];
let i2 = this.INITSTATE[2];
let i3 = this.INITSTATE[3];
const ref = this.unpack(str);
for (const item of ref) {
const mask = this.shiftpat[item];
i3 = (i3 & this.epsilon) | ((i3 & mask) >>> 1) | (i2 >>> 1) | i2;
i2 = (i2 & this.epsilon) | ((i2 & mask) >>> 1) | (i1 >>> 1) | i1;
i1 = (i1 & this.epsilon) | ((i1 & mask) >>> 1) | (i0 >>> 1) | i0;
i0 = (i0 & this.epsilon) | ((i0 & mask) >>> 1);
i1 |= i0 >>> 1;
i2 |= i1 >>> 1;
i3 |= i2 >>> 1;
}
return [i0, i1, i2, i3];
}
match(str, ambig = 0) {
if (!(ambig < this.INITSTATE.length)) {
ambig = this.INITSTATE.length - 1;
}
const s = this.state(str);
return (s[ambig] & this.acceptpat) !== 0;
}
unpack(str) {
return str.split('')
.flatMap(char => {
const code = char.charCodeAt(0);
if (code > 0xFF) {
return [(code & 0xFF00) >>> 8, code & 0xFF];
}
return [code & 0xFF];
});
}
}
一文字誤りのpatternを検出できる
文字抜け
余計な文字が入る
文字が間違っている
この解説を読んだだけでは
の頭ではわからない
少しずつ自分の言葉で噛み砕く必要がある
本体
word
:検索したい語句
list
:検索候補
func
: list
の中身を加工して渡したいときにつかう函数
2020-11-26 09:32:43 fizzSearch
の方、曖昧度別に分けられていなかったや
修正しよう
script.jsconst range = n => [...Array(n).keys()]; // [0,1,2,...,n-1]を返す
function fizzSearch({word, list, func = w => w, limit = undefined} = {}) {
// 検索keyword及び検索候補が空のときは何もしない
if (word.trim() === '' || list.length === 0) return [];
// 空白文字で区切った文字列を並び替える
const permutation = getPermutation(word.split(/\s/)).map(wordList => ` ${wordList.join(' ')} `);
// ambigの最大値を計算する
// permutationは、文字列を並び替えただけなので、どれも長さは一緒
let maxAmbig = Math.floor(permutation[0].length / 4) + 1;
maxAmbig = maxAmbig > 4 ? 4 : maxAmbig;
// ambigの値に応じて検索する
// limit < list.lengthなら検索を打ち切る
const results = [];
let matchedNum = 0;
(() => {
for (const ambig of range(maxAmbig)) {
let matches = new Set();
for (const targetWord of permutation) {
const prevSize = matches.size;
const asearch = new Asearch(targetWord);
// 検索したものを重複を取り除いて追加する
const temp = list.filter(word => asearch.match(func(word), ambig));
temp.forEach(word => matches.add(word));
matchedNum += matches.size - prevSize;
if (limit && matchedNum > limit) {
results.push([...matches]);
return;
}
}
results.push([...matches]);
}
})();
// 重複を取り除いて返す
return results.map((list, i, lists) => i === 0 ?
list:
list.filter(word => !lists[i-1].includes(word)));
}
function fizzSearch2(word, list, func = w => w) {
// 検索keyword及び検索候補が空のときは何もしない
if (word.trim() === '' || list.length === 0) return [];
// 空白文字で区切った文字列を並び替える
const permutation = getPermutation(word.split(/\s/)).map(wordList => ` ${wordList.join(' ')} `);
// ambigの最大値を計算する
// permutationは、文字列を並び替えただけなので、どれも長さは一緒
let maxAmbig = Math.floor(permutation[0].length / 4) + 1;
maxAmbig = maxAmbig > 4 ? 4 : maxAmbig;
// ambigの値に応じて検索する
const searchedLists = range(maxAmbig)
.map(i => permutation.flatMap(targetWord =>{
const asearch = new Asearch(targetWord);
return list.filter(word => asearch.match(func(word), i));
}))
// 重複を取り除く
.map((list, i, lists) => i === 0 ? list : list.filter(word => !lists[i-1].includes(word)))
.map(list => [...new Set(list)]);
//const searchedList = permutation
// .flatMap(targetWord => [...asearched(targetWord), ...hanukeSearch(targetWord, list)]);
return searchedLists;
}
import.jsimport '/api/code/takker/fizzSearch/script.js';
export default function(word, list, func = w => w) {
return fizzSearch(word, list, func);
}
↓現在使っていない
scr
と入力すると /s.*c.*r.*/
という正規表現にマッチする文字列を返す
途中まで入力すればマッチする
所々抜けがあってもマッチする
script.js// wordの歯抜け検索をlistから行い、matchした文字列のリストを返す
function hanukeSearch(word, list) {
const regexString = word
.match(/./ug)// 書記素ごとに分割
.map(char => char.replace(/[.*+?^=!:${}()|[\]\/\\]/ug, '\\$&'))// 正規表現のescape
.map(char => `${char}.*`)
.join('');
const reg = RegExp(regexString, 'ui');
return list.filter(title => reg.test(title));
}
全順序マッチング
順列を作成する関数を実装すれば良い
script.js// 重複は考慮していない
function getPermutation(list) {
if (list.length == 0) return list;
if (list.length == 1) return [list];
if (list.length == 2) return [[list[0],list[1]],[list[1],list[0]]];
return list.flatMap(first => {
const restList = list.filter(item => item !== first);
return getPermutation(restList).map(permutation => [first, ...permutation]);
});
}