豪鬼メモ

一瞬千撃

ラテン文字のマッチング用正規化

小ネタなのだが、ラテン文字のマッチング用の正規化処理を自前で書くにはどうすれば最も簡単なのか考えてみた。


自分で英和辞書と和英辞書を作るという意味不明な趣味を持つ私である。フリーの英和辞書や英辞郎のデータをDBMに入れて検索できるようにしつつ、編集距離による曖昧一致検索とか、共起頻度から推定した類語検索とかも実装して、自分だけで便利に使っている。英和辞書を使う際のスペルミスを曖昧一致で救うが実用上まず重要だ。そして英文ライティングの際には和英辞書の類語検索がとても重要だ。さらに、マッチした単語を適合性を元に並び替えるのも大事だ。例えば「喧騒」って英語でなんて言うか調べる際に、完全一致で検索するだけだと自分で類語のリストを展開して「賑やか」とか「うるさい」とか何度も検索を試さないといけない。曖昧検索と類語検索を元に展開した候補が適合性の高い順に並べられると、高い確率で欲しい情報が一撃で全て手に入る。1回のクエリに対して内部では1万回とかの検索処理をするのだが、全く待ち時間を感じさせずに応答できる。これだけでもDBMを作ってよかったなと思う。英辞郎のライセンスの関係でサービスを公開できないのがちと残念だ。

閑話休題。暇つぶしに既存の実装を新型DBMベースに置き換える作業をしているのだが、その際に検索キーの正規化処理を実装し直すことにした。文字コード周りの処理と言えばICUを使えば済むし、ガチなユースケースでは確実にそうすべきなのだが、趣味の領域では自分のユースケースに限定した軽量の実装を用意してもよかろうと。英和辞書を検索するにあたり、ラテン文字ダイアクリティカルマーク(発音区別符号)の有無を無視したマッチングがしたくなる。「résumé」のエントリを「resume」と入力した際にも引っ掛けたいということだ。ダイアクリティカルマークを外したASCII範囲の文字列を作る文字列正規化関数があれば、その結果を検索キーにすれば目的が達成できる。じゃあその正規化関数をどうやって書くか。

Unicodeの正規化で、基底文字とダイアクリティカルマーク等を単一文字に合成するNFCという処理と、その逆に基底文字とダイアクリティカルマーク等を複数文字に分解するNFDという処理が定義されている。ならば、NFCで一文字であるラテン文字にNFDを適用した場合に1文字目がASCIIの英字であれば、その英字だけを取り出すことで、正規化が完了できる。ということは、NFDのルールの中からラテン文字のサブセットを抜き出してルックアップテーブルを作れば良さそうだ。

で、都合の良いことに、UnicodeコンソーシアムのサイトにNFCやNFDのテストデータがあり、それが全てのルールを網羅している。このファイルである。これを読み込んでC++のコードを生成すればいい。セミコロンで区切られた第2フィールドがNFC、第3フィールドがNFDなので、こんなようなPythonコードでルックアップテーブルのコードが書き出せる。

import re
import sys

norm_table = {}
ascii_lower_range = range(ord('a'), ord('z') + 1)
ascii_upper_range = range(ord('A'), ord('Z') + 1)

for line in sys.stdin:
    line = line.rstrip()
    line = re.sub(" *#.*", "", line)
    fields = line.split(';')
    if len(fields) < 5:
        continue
    nfc_chars = fields[1].split(' ')
    if len(nfc_chars) != 1:
        continue
    nfc_char = int(nfc_chars[0], 16)
    nfd_chars = fields[2].split(' ')
    nfd_char = int(nfd_chars[0], 16)
    if (nfd_char not in ascii_lower_range and
        nfd_char not in ascii_upper_range):
        continue
    norm_table[nfc_char] = nfd_char

min_char = 0x00c0
max_char = 0x0233
print("static constexpr uint32_t ucs_normalize_map_min_char = 0x{:04x};".format(min_char))
print("static constexpr uint32_t ucs_normalize_map_max_char = 0x{:04x};".format(max_char))
print("static constexpr uint8_t ucs_normalize_map[] = {")
num_columns = 0
for c in range(min_char, max_char + 1):
    norm_char = norm_table.get(c) or 0
    print("0x{:02x},".format(norm_char), end="")
    num_columns += 1
    if num_columns % 16 == 0:
        print("")
if num_columns % 16 != 0:
    print("")
print("};")

で、その出力を使ってこんなようなコードが完成した。

std::wstring NormalizeLatinForMatch(const std::wstring& wstr) {
  static constexpr uint32_t ucs_normalize_map_min_char = 0x00c0;
  static constexpr uint32_t ucs_normalize_map_max_char = 0x0233;
  static constexpr uint8_t ucs_normalize_map[] = {
    0x41,0x41,0x41,0x41,0x41,0x41,0x00,0x43,0x45,0x45,0x45,0x45,0x49,0x49,0x49,0x49,
    0x00,0x4e,0x4f,0x4f,0x4f,0x4f,0x4f,0x00,0x00,0x55,0x55,0x55,0x55,0x59,0x00,0x00,
    0x61,0x61,0x61,0x61,0x61,0x61,0x00,0x63,0x65,0x65,0x65,0x65,0x69,0x69,0x69,0x69,
    0x00,0x6e,0x6f,0x6f,0x6f,0x6f,0x6f,0x00,0x00,0x75,0x75,0x75,0x75,0x79,0x00,0x79,
    0x41,0x61,0x41,0x61,0x41,0x61,0x43,0x63,0x43,0x63,0x43,0x63,0x43,0x63,0x44,0x64,
    0x00,0x00,0x45,0x65,0x45,0x65,0x45,0x65,0x45,0x65,0x45,0x65,0x47,0x67,0x47,0x67,
    0x47,0x67,0x47,0x67,0x48,0x68,0x00,0x00,0x49,0x69,0x49,0x69,0x49,0x69,0x49,0x69,
    0x49,0x00,0x00,0x00,0x4a,0x6a,0x4b,0x6b,0x00,0x4c,0x6c,0x4c,0x6c,0x4c,0x6c,0x00,
    0x00,0x00,0x00,0x4e,0x6e,0x4e,0x6e,0x4e,0x6e,0x00,0x00,0x00,0x4f,0x6f,0x4f,0x6f,
    0x4f,0x6f,0x00,0x00,0x52,0x72,0x52,0x72,0x52,0x72,0x53,0x73,0x53,0x73,0x53,0x73,
    0x53,0x73,0x54,0x74,0x54,0x74,0x00,0x00,0x55,0x75,0x55,0x75,0x55,0x75,0x55,0x75,
    0x55,0x75,0x55,0x75,0x57,0x77,0x59,0x79,0x59,0x5a,0x7a,0x5a,0x7a,0x5a,0x7a,0x00,
    0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
    0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
    0x4f,0x6f,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x55,
    0x75,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
    0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x41,0x61,0x49,
    0x69,0x4f,0x6f,0x55,0x75,0x55,0x75,0x55,0x75,0x55,0x75,0x55,0x75,0x00,0x41,0x61,
    0x41,0x61,0x00,0x00,0x00,0x00,0x47,0x67,0x4b,0x6b,0x4f,0x6f,0x4f,0x6f,0x00,0x00,
    0x6a,0x00,0x00,0x00,0x47,0x67,0x00,0x00,0x4e,0x6e,0x41,0x61,0x00,0x00,0x00,0x00,
    0x41,0x61,0x41,0x61,0x45,0x65,0x45,0x65,0x49,0x69,0x49,0x69,0x4f,0x6f,0x4f,0x6f,
    0x52,0x72,0x52,0x72,0x55,0x75,0x55,0x75,0x53,0x73,0x54,0x74,0x00,0x00,0x48,0x68,
    0x00,0x00,0x00,0x00,0x00,0x00,0x41,0x61,0x45,0x65,0x4f,0x6f,0x4f,0x6f,0x4f,0x6f,
    0x4f,0x6f,0x59,0x79,
  };
  std::wstring result;
  result.reserve(wstr.size());
  for (uint32_t wc : wstr) {
    if (wc >= ucs_normalize_map_min_char && wc <= ucs_normalize_map_max_char) {
      const uint8_t norm_char = ucs_normalize_map[wc - ucs_normalize_map_min_char];
      if (norm_char > 0) {
        wc = norm_char;
      }
    }
    result.push_back(wc);
  };
  return result;
}

ICUという便利なライブラリがあるのでこんなことを自分でやる必要性は全くない。しかし、ちょっと自分なりのカスタマイズをしたいような場合も出てくるので、正規化処理を自分でも書けるという引き出しを持っておくことは有用であろう。