JavaScript：Nグラムで文字列検索する関数

January 25, 2022

こんな感じで文字列を検索したい時に使える関数をご紹介します。

const names = [
  'ほしの ユタカ',
  'つきもと マコト',
  'かざま リュウイチ',
  'さくま マナブ',
  'こん ウェンガ',
];

const res1 = search(names, 'ユタカ'); // 'ほしの ユタカ' が返ってきて欲しい。
const res2 = search(names, 'きもと'); // 'つきもと マコト' が返ってきて欲しい。

補足

N グラム(n-gram)

任意の文字列や文書を連続した n 個の文字で分割するテキスト分割方法．特に，n が 1 の場合をユニグラム（uni-gram），2 の場合をバイグラム（bi-gram），3 の場合をトライグラム（tri-gram）と呼ぶ．最初の分割後は 1 文字ずつ移動して順次分割を行う．図書館情報学の分野では，検索システムにおける索引の自動抽出においてよく用いられる．例えば，「図書館情報学」をバイグラムで分割すると，「図書」「書館」「館情」「情報」「報学」となる．形態素解析を行って単語境界を識別して分割する方式と比べ，検索漏れが起きにくい，分割が機械的で容易なため多言語への対応が容易などの長所がある．しかし，情報検索や自動分類へ応用する際にはノイズが多くなる，転置ファイルのサイズが大きくなるなどの短所がある．

N グラムとは - コトバンク

実装する #

ここでは TypeScript で記述します。

検索処理に必要なパーツごとに関数を作っていきます。

ノーマライズ処理 #

表記ブレを補正する処理です。

const normalize = (text: string): string => {
  text = text.replace(/\s+/g, ''); // 半角スペースを取り除く
  text = text.replace(/[\u3041-\u3096]/g, (c) => String.fromCharCode(c.charCodeAt(0) + 0x60)); // ひらがなをカタカナに変換する
  text = text.normalize('NFKC'); // https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/String/normalize
  text = text.toLowerCase(); // 大文字を小文字に変換する
  return text;
};

N グラム処理 #

N 文字に分割する処理です。

uni-gram , bi-gram , tri-gram それぞれ作っておきます。

const nGramize = (n: number, text: string): string[] => {
  const tokens: string[] = [];
  const { length } = text;
  if (length < n) {
    return tokens;
  }
  let i = length - n + 1;
  while (i--) {
    tokens[i] = text.slice(i, i + n);
  }
  return tokens;
};

const uniGramize = (text: string): string[] => {
  return nGramize(1, text);
};

const biGramize = (text: string): string[] => {
  return nGramize(2, text);
};

const triGramize = (text: string): string[] => {
  return nGramize(3, text);
};

トークン化処理 #

文字列をトークン化する処理です。上記で用意した関数を組み合わせます。

今回は uni-gram で試します。

const tokenize = (text: string): string[] => {
  return uniGramize(normalize(text));
};

これを実行すると以下のような結果が取得できます。

const res = tokenize('ほしの ユタカ'); // ["ホ", "シ", "ノ", "ユ", "タ", "カ"]

例えばここで bi-gram , tri-gram を使用すると結果は以下になります。

const res1 = tokenize('ほしの ユタカ'); // ["ホシ", "シノ", "ノユ", "ユタ", "タカ"]
const res2 = tokenize('ほしの ユタカ'); // ["ホシノ", "シノユ", "ノユタ", "ユタカ"]

検索処理 #

上記で作成したトークン化処理の関数を利用して検索します。

const search = (source: string[], text: string): string[] => {
  const tokens = tokenize(text);
  const sourceMaps = source.reduce((acc, val) => {
    return [...acc, { key: val, token: tokenize(val) }];
  }, [] as { key: string; token: string[] }[]);
  const hitted = sourceMaps.filter((map) => {
    return tokens.every((token) => {
      return map.token.includes(token);
    });
  });
  return hitted.map((data) => data.key);
};

実行結果 #

以下は uni-gram で実行しています。意図した通りに動いていることが確認できました。

const res1 = search(names, 'ユタカ'); // ["ほしの ユタカ"]
const res2 = search(names, 'きもと'); // ["つきもと マコト"]
const res3 = search(names, 'ま'); // ["つきもと マコト", "かざま リュウイチ", "さくま マナブ"]
const res4 = search(names, '  うぇ こん    が'); // ["こん ウェンガ"]