ナード戦隊データマン

機械学習と自然言語処理についてのブログ

soundex: もしかして検索に使えそうなアルゴリズム

表音アルゴリズム(phonetic algorithm)とは、発音で語をインデクシングする方法です。ここでは、jellyfishというライブラリを使って、"natural language processing"のような語に似た語を作ってみます。

soundexとは

soundexはphonetic algorithmの一つで、発音的に語をエンコードします。

  1. 最初の文字を取得し、共起するa,e,i,o,u,y,h,wを削除。
  2. 以下のルールに従って先頭から数文字に対して数値変換:
    1. b,f,p,v -> 1
    2. c,g,j,k,q,s,x,z -> 2
    3. d, t -> 3
    4. l -> 4
    5. m, n -> 5
    6. r -> 6

これを使っていきます。

事前準備

  1. ボキャブラリーをダウンロードします。 https://github.com/sugiyamath/fuzzy_matching_experiments/blob/master/vocab.json
  2. jellyfishをインストールします。

コード

# coding: utf-8
import jellyfish as jf
from collections import defaultdict
import random
import math

def chooseit(word, data, func, size=1.0):
    word_l = word.lower()
    tmp = [x for x in data[func(word_l)] if x[0] not in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ']
    result = random.choice(tmp[:int(len(tmp)*size)+1])
    return result

def xfy(target, data, func):
    out = []
    for word in target.split():
        out.append(chooseit(word, data, func))
    return out


def build_data(vocab, func):
    data = defaultdict(list)
    for v in vocab:
        try:
            data[str(func(v))].append(v)
        except:
            continue
    return data

if __name__ == "__main__":
    import sys
    import json
    import numpy as np
    with open("vocab.json") as f:
        vocab = json.load(f)
    target = sys.argv[1]
    enc = jf.soundex
    data = build_data(vocab, enc)
    out = []
    for i in range(30):
        out.append(' '.join(xfy(target, data, enc)))

    for x in sorted(np.unique(out).tolist()):
        print(x)

実行

python test.py "natural language processing"

[結果]

naturale linguos paracycling
naturalia languages prosocial
naturalia lmshouses processions
naturalisation lengas prakasar
naturalises lingues progestogens
naturalistes lincosamides praecisa
naturalistic longicervia percygarnhami
naturalization linguists persicaria
naturalization longicaudus projectivities
naturalized longistaminea precusor
naturalizes languageless purchasable
naturalizing longicirrum perigees
naturelles longistriga projectiles
natürliche longistyla presacrals
natürlicher linguicism peroxycarbonate
nderlying languages pirgos
ndorla language przeciwko
neutralises línguas phorcas
neutralism linkages pyrgos
neutrality lancashire persecutor
neutralized longicornuta praeses
neutralizes lunches prakasa
neutrals lengkuas preassigned
nitrilase linches precession
nitrilotriacetic longicanalis paroxysmal
nitroalkenes lancashire persisters
nitryl linecasting persister
notarial longicorpus percussed
nterwolde longistaminata persica
ntireligious languages progestogen

なお、jf.soundexを指定している部分に、jf.metaphoneを指定すると以下のような結果に変わります。

natural langage precising
naturale langage precising
naturale langage processing
naturale language precessing
naturali langage processing
naturalia linguaggio precessing
naturall lenguaje precessing
naturall linkage precising
naturel language processing
naturel linguaggio processing
neutrally language processing
nitrile lenguaje precising
nitrile linguaggio processing
nitrile linkage precising
nitryl lenguaje processing
nitryl linguaggio precising
nitryl linkage precising
notarial linguaggio precessing
notarial linkage precessing
notarial linkage precising
notarially linguaggio processing
notorial linkage precessing
ntirely langage precising
ntirely language precising
ntirely linguaggio precising
ntirely linkage processing

metaphoneの詳細は以下: https://en.wikipedia.org/wiki/Metaphone

より現実的な使い方

インデクシングされた各単語が、クエリ内で使われた頻度によってソートすることにより、「もしかして」検索に近いものが実装できる気がします。

上記例では、"natural language processing"のような語を空白でsplitしましたが、単に先頭文字だけをとってエンコードする方法も考えられます。

手順としては、

  1. クエリが入力される。
  2. クエリを複数の方法でエンコードする。
  3. エンコードしたものを、soundex等でインデクシングされているシステムから検索。
  4. その中でもっとも頻度の多いものを選び出す。
  5. 最も頻度の多いものと一致していなければ、「もしかして」を提案する。

のような方法を考えることができそうです。

リンク

https://pypi.org/project/jellyfish/