JavaScriptで絞り込み検索の実装

大量のタグやキーワードの中から検索をかけるとき、最近はテキストに入力しながらリアルタイムで検索してくれる機能をよく見ますね。 私の趣味プログラミングでも、「めもりあん」のタグ検索機能でこのような処理を実装しています。

(こんなかんじ)

f:id:piyorinpa:20171203234600g:plain

単純に配列の値を入力値で検索させると、最悪、配列の要素数分の処理が必要になりそうです。リアルタイム入力の場合、刻々とテキストボックスの内容が変化するので、ちょっとしんどそうです。 そこで、連想配列を用いて検索させるようにしてみました。

(詳しい実装はソースコードを見てみてください)

(動作のサンプルはこちらから)

たとえば、「ひよこ」「ひよこまめ」「あひる」「ひもの」の4つの要素に対してリアルタイム検索しようとしたときに、以下のようにキー値を定めて辞書を作ります。

var indexes={};
indexes["あ"] = ["あひる"];
indexes["ひ"] = ["ひよこ", "ひよこまめ", "ひもの"];
indexes["ひよ"] = ["ひよこ", "ひよこまめ"];
indexes["ひよこ"] = ["ひよこ", "ひよこまめ"];
indexes["ひよこま"] = ["ひよこまめ"];

これなら、入力値が「ひ」のときは、indexes["ひ"]の中身をすべて拾ってあげればよいので、配列を全探索しなくてもよさそうです。

しかし、実際に検索したいアイテムはこんな感じのデータ構造だったりします。

var listData = [
    {data: { name: "ひよこ" } },
    {data: { name: "ひよこまめ" } },
    {data: { name: "あひる" } },
];

listData内のdata.nameに検索対象が存在しており、リアルタイム検索することで最終的にはlistDataの要素を取り出したいのです。

このようなデータ構造に加えて、先ほど説明した「辞書を作って検索する方針」に基づき処理を実装してみます。

(以下の解説を読んでいただく前に、ソースコードの全体を眺めたほうがいいかもです)

まずは、辞書作りから。

export default class arraySearcher{
    constructor(maxHashLength = 1){
        this._index = {};   //辞書データ
        this._arr = {};       //検索対象データ
        this._relation = null;   //(後で説明します)
        this.maxHashLength = maxHashLength;   // 辞書文字列の最大長さ
    }

こんな感じ宣言をします。今回の場合、検索対象データとはlistData.data.name のことです。

また、辞書データのキー値の最大長さを設定できるようにすることで、辞書データが大きくなりすぎないようにします。 (たとえば、maxHashLength=2のときに"かいだん" を登録すると、_index["か"] _index["かい"] が生成されるようにします)

つづいて、辞書を登録する処理をば。

setHash(objArray, valueKeys){
    this._relation = {};
    this._index = {};
    this._arr = [];
    objArray.forEach( item => {
        let value = item;
        valueKeys.forEach( valueKey => { value = value[valueKey] });
        this._relation[value] = { item: item, value: value };
        this._arr.push(value);
    });
    this._makeHash();
}

このようにすることで、たとえばsetHash(listData, ["data", "name"]); としてあげれば、_arr にはobjArrayからnameの値を取り出した配列["ひよこ", "ひよこまめ", "あひる"]が得られます。

また、_relationobjArrayの要素(つまりlistDataの要素)とnameの値の関連性を記述することで、あとで検索結果からlistDataの要素を返せるようにしておきます。 (このとき、_relationのキー値を検索対象値(nameの値)とすることがポイントになります)

_makeHash(){
    this._arr.forEach( item => {
        for( var i=1; i<=this.maxHashLength; i++){
            let hashstr = item.substr(0, i);            //文字を切り出す
            if( hashstr === "" ) break;                 //文字が空なら処理を終了
            if( this._index[hashstr] ){                 //既に辞書のキーが存在する場合は追加
                this._index[hashstr].push(item);
            }
            else{                                       //まだキーが存在しなければ登録
                this._index[hashstr] = [item];
            }
        }
    });
}

つぎに、上記の処理を実行することで、_indexに辞書データを作ります。これで先ほど説明した方針で、検索ができるようになりました。

_getObj(arrItems){
    if( !arrItems ) return [];
    return arrItems.map( arrItem => this._relation[arrItem] );
}

search(keyword){
    let results = [];
    if( keyword.length <= this.maxHashLength ){
        results = this._getObj(this._index[keyword]);
    }
    else{
        let keywordHash = keyword.substr(0, this.maxHashLength);
        let objs = this._getObj(this._index[keywordHash]);
         objs.forEach( obj => {
            if( obj.value.includes(keyword) ) results.push(obj)
        } );
    }
    return this._relation ? results.map( obj => obj.item ) : results;
}

var result = searcher.search('検索文字列');とすることで検索します。もし検索文字列の長さが辞書の最大キー値よりも小さければ、単に辞書リストを返せばよいので簡単です。

そうでない場合は、最もよく一致する辞書内のアイテムから、さらにString.includes()を使って絞り込みます。検索文字列が文字が含まれていれば検索結果として返すようにします。

ここで、さきほどの_relation の情報を使い、検索結果にヒットする name を持つdataを返すことができます。

こんな感じで実装してみて、いまのところは困っていませんが、大量のデータを用いて検索速度を検証したりしていないので、もしかしたら粗があるかもです。 (とりあえず、配列数に比例して検索が耐えられなくなる状況はある程度緩和できそうかな、という気持ちです。)

ではでは。