fizzSearch

/icons/hr.icon

あいまい検索クラス

ambiguous text search

cf.

課題

検索を途中で打ち切る

最大n件しか使わないなら、それ以上検索する必要がない

高速化を期待できる

並列で検索している場合も使える

個々のworkerごとに検索数上限を設定するのは計算が難しいが、代わりに最終的な検索数上限をつかえばいい

2020-11-19 08:37:14 やってみた

検索語句に最も関連している順に並び替えしたい

対策

類似度を数値化し、それを元に並べ替える

完全一致、一文字間違い、2文字間違い、……と並べることができる

もうちょっと高速化したい

検索対象の前後に空白を入れることで解決した

ひらがな/カタカナ/ｶﾀｶﾅを区別しないで検索できるようにしたい

検索候補と、検索文字列とを全てひらがな/alphabetに変換してから検索を開始する

Asearchに渡す前に変換すればいいかな？

あまり負荷がかかるようであれば、予め利用者側で変換済みの文字列を用意してもらうという手もある

更新とか

2020-11-02 10:38:03

検索keyword or 検索候補がからのときは、0件の検索結果を返すようにした

検索keywordに空白を与えると固まる問題への対処

2020-10-15 15:38:33

あいまい度順に検索結果が並ぶようにした

2020-10-12 01:48:50

limitCount <= 4

2020-09-17 20:34:24

2020-09-17 11:30:57

code:script.js

class Asearch {

get INITPAT() {return 0x80000000;} // 0100,0000,0000,0000,0000,0000,0000,0000

get MAXCHAR() {return 0x100;}

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 {

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 = '') {

const ref = this.unpack(str);

for (const item of ref) {

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;

}

}

match(str, ambig = 0) {

if (!(ambig < this.INITSTATE.length)) {

ambig = this.INITSTATE.length - 1;

}

const s = this.state(str);

}

unpack(str) {

return str.split('')

.flatMap(char => {

const code = char.charCodeAt(0);

if (code > 0xFF) {

}

});

}

}

一文字誤りのpatternを検出できる

文字抜け

余計な文字が入る

文字が間違っている

少しずつ自分の言葉で噛み砕く必要がある

本体

修正しよう

code:script.js

function fizzSearch({word, list, func = w => w, limit = undefined} = {}) {

// 検索keyword及び検索候補が空のときは何もしない

if (word.trim() === '' || list.length === 0) return [];

// 空白文字で区切った文字列を並び替える

// ambigの最大値を計算する

// permutationは、文字列を並び替えただけなので、どれも長さは一緒

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) {

return;

}

}

}

})();

// 重複を取り除いて返す

return results.map((list, i, lists) => i === 0 ?

list:

}

function fizzSearch2(word, list, func = w => w) {

// 検索keyword及び検索候補が空のときは何もしない

if (word.trim() === '' || list.length === 0) return [];

// 空白文字で区切った文字列を並び替える

// ambigの最大値を計算する

// permutationは、文字列を並び替えただけなので、どれも長さは一緒

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));

}))

// 重複を取り除く

//const searchedList = permutation

return searchedLists;

}

code:import.js

import '/api/code/takker/fizzSearch/script.js';

export default function(word, list, func = w => w) {

return fizzSearch(word, list, func);

}

↓現在使っていない

途中まで入力すればマッチする

所々抜けがあってもマッチする

code:script.js

// wordの歯抜け検索をlistから行い、matchした文字列のリストを返す

function hanukeSearch(word, list) {

const regexString = word

.match(/./ug)// 書記素ごとに分割

.join('');

const reg = RegExp(regexString, 'ui');

return list.filter(title => reg.test(title));

}

全順序マッチング

順列を作成する関数を実装すれば良い

code:script.js

// 重複は考慮していない

function getPermutation(list) {

if (list.length == 0) return list;

return list.flatMap(first => {

const restList = list.filter(item => item !== first);

});

}