わが家の脱・料理属人化プロジェクト、基本機能編の 4 回目です。
前回は、材料や手順をまとめて貼り付け、材料を名前と分量に分ける工夫を紹介しました。
入力が楽になってレシピが増えてくると、今度は登録したレシピを探す手間が気になってきます。
今回は、レシピの検索の仕組みを紹介します。
- 導入編はこちら → わが家の料理属人化を解消したくて、家族専用のレシピアプリを作った（導入編）
- アプリ全体像はこちら → 家族のレシピアプリの全体像 - Firebase と Cloudflare Workers でコスト 0 で運用（基本機能編 1）
- 前回はこちら → 家族のレシピアプリ - 「しょうゆ…大さじ1」を正規表現で名前と分量に分ける（基本機能編 3）
困っていたこと
レシピが増えてくると、一覧をたどるより検索で探すことが多くなります。
ところが、家族で登録していると、同じ食材でも書き方がそろいません。
- 玉ねぎ／たまねぎ／タマネギ／玉葱
- にんじん／人参／ニンジン
- 豚ひき肉／豚挽肉／豚挽き肉
そのため、「たまねぎ」で検索しても、「玉葱」と書いたレシピが出てきません。
しかも、登録した本人も、自分が漢字で書いたことを覚えていません。
外部の検索サービスは使わない
全文検索のサービスを使う手もありますが、今回は使わないことにしました。
理由は次の 3 つです。
- スーパーや台所でも検索したい
→ 電波が弱い場所でも、オフラインのまま検索できるようにするため - 運用コストは 0 円にしたい
→ 有料のサービスや、無料枠の小さいサービスは使えないため - 家族のレシピは多くても数百件
→ 端末に全件を持っているので、端末で全件を確かめても十分に速いため
そこで、端末の中で、表記ゆれをなくした形どうしを比べることにしました。
表記ゆれは、次の 2 段階でなくします。
- 全角と半角、大文字と小文字、カタカナとひらがなの違いをなくす
- 表記ゆれ辞書で、同じ語の書き方を代表の語に置き換える
文字の違いをなくす
まず、全角と半角、大文字と小文字、カタカナとひらがなの違いをなくします。
const KATAKANA = /[ァ-ヶ]/g;
const KATAKANA_TO_HIRAGANA = 0x60;
/** 全角と半角（NFKC）、大文字と小文字、カタカナとひらがなの違いをなくす */
export function normalizeText(text: string): string {
return text
.normalize('NFKC')
.toLowerCase()
.replace(KATAKANA, (char) => String.fromCharCode(char.charCodeAt(0) - KATAKANA_TO_HIRAGANA));
}
Unicode では、カタカナとひらがながちょうど 0x60 ずれて並んでいます。
そのため、文字コードから 0x60 を引くだけでひらがなに変換できます。
これで、「タマネギ」と「たまねぎ」は同じになります。
しかし、「玉葱」と「玉ねぎ」は同じにならないため、ここからは辞書の出番です。
表記ゆれ辞書を作る
よく使う食材・調味料・料理の書き方の違いを辞書にまとめました。
各組の先頭が代表の語です。
/**
* 表記ゆれ辞書。よく使う食材・調味料・料理の、同じ語の書き方の違いをまとめる。
*/
export const SPELLING_VARIANTS: readonly (readonly string[])[] = [
// 野菜
['玉ねぎ', 'たまねぎ', '玉葱'],
['ねぎ', '葱'],
['長ねぎ', 'ながねぎ'],
['にんじん', '人参', '人蔘'],
['かぼちゃ', '南瓜'],
// …
];
辞書づくりでいちばん悩んだのは、入れない語のほうでした。
入れないことにしたのは、主に次の 2 種類です。
- 別の言葉で同じものを指す語（「大葉」と「青じそ」など）
→ まとめると「大葉で検索したのに、青じそのレシピが出てきた」という意外な結果になるため - ほかの語の一部になりやすいひらがな（梨・鯛・牡蠣の「なし」「たい」「かき」など）
→ 「砂糖なし」の「なし」まで置き換わり、「砂糖梨」になってしまうため
辞書は、語を足すほど、関係のないレシピまで引っかかりやすくなります。
そのため、何を入れるかより、何を入れないかの判断のほうが大事でした。
Trie で、最も長い語を置き換える
正規化した文字列の中から辞書の語を探し、代表の語に置き換えます。
ただ、辞書の語を 1 つずつ replaceAll で置き換えると、置き換える順番によって結果が変わってしまいます。
たとえば「合挽き肉」は、辞書では「合いひき」の組に入っています。
しかし、先に「挽き肉」→「ひき肉」を置き換えると「合ひき肉」になり、「合いびき肉」と書いたレシピ（→「合いひき肉」）と一致しなくなります。
そこで、辞書を Trie（1 文字ずつたどる木）にして、文字列の各位置から始まる最も長い語を探すことにしました。
interface TrieNode {
children: Map<string, TrieNode>;
/** ここで終わる語の代表の語 */
canonical?: string;
}
/** 表記ゆれ辞書を、正規化した語の木にする（初めて使うときに 1 回だけ作る） */
function getDictionary(): TrieNode {
// （一部を省略）
}
function replaceVariantsOnce(text: string): string {
const root = getDictionary();
let result = '';
let i = 0;
while (i < text.length) {
// ここから始まる最も長い語を探す
let node: TrieNode | undefined = root;
let matchEnd = -1;
let matchCanonical = '';
for (let j = i; j < text.length; j++) {
node = node.children.get(text[j] ?? '');
if (!node) {
break;
}
if (node.canonical !== undefined) {
matchEnd = j + 1;
matchCanonical = node.canonical;
}
}
if (matchEnd === -1) {
result += text[i];
i += 1;
} else {
result += matchCanonical;
i = matchEnd;
}
}
return result;
}
辞書の木は、初めて検索したときに 1 回だけ作ります。
辞書の語も、normalizeText を通した形で木に入れておきます。
置き換えた結果が、さらに別の語になることもあります（「炒り胡麻」→「炒りごま」→「いりごま」）。
そのため、結果が変わらなくなるまで、最大 3 回繰り返しています。
export function replaceSpellingVariants(normalized: string): string {
let current = normalized;
for (let i = 0; i < 3; i++) {
const next = replaceVariantsOnce(current);
if (next === current) {
break;
}
current = next;
}
return current;
}
入力の途中でも見つける
ここで 1 つ問題が出ました。
検索は 1 文字打つごとに絞り込むため、入力の途中でもレシピが見つかってほしいところです。
たとえば「たまね」まで打ったときは、次のようになります。
- 検索語の「たまね」は、辞書の語になりきっていないので、置き換わらない →「たまね」
- レシピ側の「たまねぎ」は、辞書で置き換わる →「玉ねぎ」
置き換えた形どうしで比べると、「玉ねぎ」は「たまね」を含まないので見つかりません。
そこで、置き換えた形と、正規化しただけの形の両方を持ち、どちらかで含んでいれば見つかったことにしました。
/** 検索に使う形。正規化しただけの形と、表記ゆれ辞書で置き換えた形の両方を持つ */
export interface SearchKey {
normalized: string;
canonical: string;
}
/** 検索の対象の文字列を検索に使う形にする。空白は無視する */
export function toSearchKey(text: string): SearchKey {
const normalized = normalizeText(text).replace(WHITESPACE, '');
return { normalized, canonical: replaceSpellingVariants(normalized) };
}
/**
* 対象が検索語を含むか。
* 入力の途中（例: 「玉ね」）でも見つかるよう、正規化しただけの形どうしでも比べる
*/
export function includesSearchKey(target: SearchKey, word: SearchKey): boolean {
return target.normalized.includes(word.normalized) || target.canonical.includes(word.canonical);
}
ただし、「玉葱」と書いたレシピは、「たまね」の時点ではまだ見つかりません。
「たまねぎ」まで打ち切ると、両方が「玉ねぎ」に置き換わって見つかります。
検索語は空白で区切り、すべての語を含むレシピを表示します（AND 検索）。
検索の対象は、料理名と材料の名前です。
レシピ側の検索に使う形は、レシピごとに 1 回だけ作って WeakMap に置いています。
レシピが変わるとオブジェクトが入れ替わるので、キャッシュを捨てる処理を書かずに済みます。
// 検索・並べ替えに使う形はレシピごとに 1 回だけ作る。レシピが変わるとオブジェクトが入れ替わるため、作り直しになる
const SEPARATOR = '\u0000';
const searchKeyCache = new WeakMap<BrowsableRecipe, SearchKey>();
function searchKeyOf(recipe: BrowsableRecipe): SearchKey {
let key = searchKeyCache.get(recipe);
if (!key) {
// 欄をまたいで一致しないよう、区切りの文字を挟む
const keys = [recipe.title, ...recipe.ingredients.filter((ingredient) => ingredient.kind === 'item').map((ingredient) => ingredient.name)].map(
toSearchKey
);
key = { normalized: keys.map((k) => k.normalized).join(SEPARATOR), canonical: keys.map((k) => k.canonical).join(SEPARATOR) };
searchKeyCache.set(recipe, key);
}
return key;
}
料理名と材料の名前をそのままつなぐと、前の欄の最後と次の欄の最初がくっついて、意図しない語ができてしまいます。
たとえば、材料に「ごま」と「豆腐」が続けて並んでいると、「ごま豆腐」で検索したときに引っかかります。
そのため、欄の間に \u0000 を挟んで、欄をまたいだ一致を防いでいます。
買い物リストでも同じ規則を使う
この正規化は、買い物リストで同じ品名をまとめるときにも使っています。
妻が「玉ねぎ」、私が「タマネギ」を足しても、買い物リストでは 1 行にまとまります。
検索と買い物リストで規則がずれると、「検索では同じ扱いなのに、買い物リストでは別の行になる」というちぐはぐなことが起きます。
そのため、同じ関数を共有のパッケージに置いて、両方から使っています。
まとめ
外部の検索サービスは使わず、端末にある全件を、表記ゆれをなくした形で比べるようにしました。
文字の違いをなくしてから表記ゆれ辞書で代表の語に置き換え、入力の途中でも見つかるよう、置き換える前と後の両方の形で比べています。
次回は、買い物リストの話を予定しています。