文字列が格納された配列をGoogleのように検索する

(この記事はQiitaで僕が書いたものを移行した記事です。記事中のコメントはQiitaの該当記事を参照ください)

Google検索のように A or Bみたいに検索可能にしました。

配列を探索して当てはまった要素を抜き出した新しい配列を返します。元の配列に変更を加えません。

""(ダブルクォーテーション)で囲むとスペースを含めて検索できます。 NOT検索にはまだ対応してません。 対応させました。

サンプル

サンプルでは京都の区名を格納した配列を検索しています。

var arr = ['kitaku', 'kamigyōku', 'sakyōku', 'nakagyōku', 'higashiyamaku', 'shimogyōku', 'minamiku', 'ukyōku', 'fushimiku', 'yamashinaku', 'nishikyōku'];
search(arr, 'kita or higashiyama');

また、配列のみでなくオブジェクトのプロパティも検索可能です。

var data = [{ name: 'Bob', age: 40}, { name: 'Alis', age: 19}, { name: 'Michael', age: 34}, { name: 'Jonathan', age: 98}];
search(data,'Bob', function(obj) {return obj.name});

特徴

• キーワードに含まれる連続したスペース、全角スペースなどを削除してスペースに置き換えます。タブ文字、改行もスペースに変換されます
• and orのほかに「かつ」、「または」、「&&」、「||」、「 (半角スペース)」を使えます。半角スペースはandと同等です。これらを使うと '(kita または higashiyama) && ku' というキーワードでも検索できます。
• 日本語にも対応しています。ただし、indexOfメソッドを使っているだけのため、「漢字」をキーワードとしても、「常用漢字」はヒットしますが「かんじ」にはヒットしません。同様に「かんじ」で検索しても「漢字」にはヒットしません。

注意

lodashを使用しています。そのため、lodashを読み込まないと動きません。

ライブラリ本体

var OTHERS = 0;
var OPERATOR = 1;
var LPARENTHESES = 2;
var RPARENTHESES = 3;

function splitExpression(exp) {
    var res = [];
    var isInString = false;
    var start = 0;
    exp = exp.replace(/[\n\t　]/g, ' ');
    exp = exp.replace(/^\s+/, '').replace(/\s+$/, '');
    for (var i = 0, _i = exp.length; i < _i; i++) {
        var nowChar = exp.charAt(i);
        if (isInString) {
            if (nowChar === '"') {
                isInString = false;
                start = i + 1;
            } else if (nowChar === '\\') {
                i += 1;
            }
        } else {
            if (nowChar === '"') {
                exp = exp.substring(0, start) + exp.substring(start, i).replace(/\s{2,}/g, ' ') + exp.substring(i);
                isInString = true;
            }
        }
    }
    if (start == 0) {
        exp = exp.substring(start, i).replace(/\s{2,}/g, ' ');
    }
    start = 0;
    isInString = false;
    for (var i = 0, _i = exp.length; i < _i; i++) {
        var nowChar = exp.charAt(i);
        if (isInString) {
            if (nowChar === '"') {
                isInString = false;
            } else if (nowChar === '\\') {
                i += 1;
            }
        } else {
            if (nowChar === '"') {
                isInString = true;
            } else if (nowChar === ' ') {
                if (exp.substring(start, i) !== '') {
                    res[res.length] = [exp.substring(start, i), OTHERS];
                }
                var operator = {
                    ' ': '&&',
                    ' and ': '&&',
                    ' かつ ': '&&',
                    ' && ': '&&',
                    ' or ': '||',
                    ' または ': '||',
                    ' || ': '||'
                };
                var matchedOperator = exp.substr(i).match(/^ (?:and|&&|かつ|or|\|\||または) |^ /)[0];
                if (operator[matchedOperator] !== '') {
                    res[res.length] = [operator[matchedOperator], OPERATOR];
                }
                start = i + matchedOperator.length;
                i += matchedOperator.length - 1;
            } else if (nowChar === '(' || nowChar === ')') {
                if (exp.substring(start, i) !== '') {
                    res[res.length] = [exp.substring(start, i), OTHERS];
                }
                if (nowChar !== '') {
                    res[res.length] = [nowChar, nowChar === '(' ? LPARENTHESES : RPARENTHESES];
                }
                start = i + 1;
            }
        }
    }
    if (exp.substring(start) !== '') {
        if (exp.substring(start) !== '') {
            res[res.length] = [exp.substring(start), OTHERS];
        }
    }
    return res;
}

function shuntingYard(formula) {
    var stack = [];
    var output = [];
    var priority = {
        '||': 0,
        '&&': 1
    };
    for (var i = 0, _i = formula.length; i < _i; i++) {
        if (formula[i][1] === OTHERS) {
            output[output.length] = formula[i].concat();
        } else if (formula[i][1] === OPERATOR) {
            var o1 = formula[i][0];
            if (stack[stack.length - 1]) {
                var o2 = stack[stack.length - 1][0];
                if (priority[o1] <= priority[o2]) {
                    output[output.length] = stack.pop();
                }
            }
            stack[stack.length] = formula[i];
        } else if (formula[i][1] === LPARENTHESES) {
            stack[stack.length] = formula[i];
        } else if (formula[i][1] === RPARENTHESES) {
            while (stack[stack.length - 1][1] !== LPARENTHESES) {
                output[output.length] = stack.pop();
                if (stack.length === 0) {
                    throw 'found mismatched parentheses';
                }
            }
            stack.pop();
        }
    }
    while (stack.length > 0) {
        if (stack[stack.length - 1][1] === LPARENTHESES) {
            throw 'found mismatched parentheses.';
        }
        output[output.length] = stack.pop();
    }
    return output;
}

function test() {
    var data = ['kitaku', 'kamigyōku', 'sakyōku', 'nakagyōku', 'higashiyamaku', 'shimogyōku', 'minamiku', 'ukyōku', 'fushimiku', 'yamashinaku', 'nishikyōku'];
    var keywords = ['ku and kita', 'kita', 'kami and kita', 'kami or kita', '(kita または higashiyama) && ku'];
    var expect = [
        ['kitaku'],
        ['kitaku'],
        [],
        ['kamigyōku', 'kitaku'],
        ['higashiyamaku', 'kitaku']
    ];
    for (var i = 0, _i = keywords.length; i < _i; i++) {
        console.log(_.isEqual(search(data, keywords[i]).sort(), expect[i]));
    }
    var data = [{ name: 'Bob', age: 40},
        { name: 'Alis', age: 19},
        { name: 'Michael', age: 34},
        { name: 'Jonathan', age: 98}];
    var keywords = ['Bob', 'Alis', 'Bob or Alis', 'o'];
    var expect = [
        [{ 'name': 'Bob', 'age': 40 }],
        [{ 'name': 'Alis', 'age': 19 }],
        [{ 'name': 'Bob', 'age': 40 }, { 'name': 'Alis', 'age': 19 }],
        [{ 'name': 'Bob', 'age': 40 }, { 'name': 'Jonathan', 'age': 98 }]
    ];
    for (var i = 0, _i = keywords.length; i < _i; i++) {
        console.log(_.isEqual(search(data, keywords[i], function(obj) {
            return obj.name;
        }).sort(), expect[i]));
    }
}

function search(arr, exp, predicate) {
    if (typeof predicate !== 'function') {
        predicate = _.identity;
    }
    exp = shuntingYard(splitExpression(exp));
    var term = '';
    var stack = [];
    for (var i = 0, _i = exp.length; i < _i; i++) {
        var term = exp[i];
        if (term[1] === OTHERS) {
            stack.push([]);
            for (var j = 0, _j = arr.length; j < _j; j++) {
                if (term[0].charAt(0) === '-' && predicate(arr[j]).indexOf(term[0].substring(0)) === -1 || term[0].charAt(0) !== '-' && predicate(arr[j]).indexOf(term[0]) !== -1) {
                    stack[stack.length - 1].push(j);
                }
            }
        } else if (term[1] === OPERATOR) {
            var b = stack.pop();
            var a = stack.pop();
            if (term[0] === '&&') {
                stack.push(_.intersection(a, b));
            } else if (term[0] === '||') {
                stack.push(_.union(a, b));
            }
        }
    }
    return _.map(stack.pop(), function(n) {
        return arr[n];
    });
}
test();