近似文字列アルゴリズムのgestalt pattern machingについてメモ

Google 検索でタイポをすると、意図したであろう綴りを教えてくれたり、意図通りの検索結果を返してくれる。

 

google-did-you-mean

このスペルチェック機能では、入力文字列が本来の文字列とどのくらい似ているのかを評価するアルゴリズムが肝で、編集距離のアルゴリズムはよくしられている。

ふとしたことから、Ratcliff/Obershelp pattern recognition(gestalt pattern maching ともいう) という編集距離とは別のアルゴリズムに出くわした。
このアルゴリズムは1980年代から存在するが、より利便性の良いアルゴリズムが発明されていったからなのか、wikipedia に載っていないくて、手元のアルゴリズム本にもみあたらない。

まだこのアルゴリズムが輝いていた 1988 年に、 Dr. Dobb’s Journal に発表された次の記事(サンプル実装はアセンブリ言語!)を元にこのアルゴリズムをメモ。

John W. Ratcliff and David Metzener, Pattern Matching: The Gestalt Approach, Dr. Dobb’s Journal, page 46, July 1988.
http://www.drdobbs.com/database/pattern-matching-the-gestalt-approach/184407970

gestalt の意味

記事の冒頭で gestalt の意味が説明されている。

Gestalt is a word that describes how people can recognize a pattern as a functional unit that has properties not derivable by summation of its parts. For example, a person can recognize a picture in a connect-the-dots puzzle before finishing or even beginning it.
This process of filling in the missing parts by comparing what is known to previous observations is called gestalt.

アルゴリズム

基本的な処理の流れは

  • 2つの文字列の最長共通部分列を再帰的に求め
  • 「共通文字列/全体の文字列」で類似度をスコア化する。

スコアは0から1までの値を取り、「1」に近いほど、類似度は高い。

gestalt pattern maching in action

例として absolute と obsolete の類似度を求めてみる。(文字列が似通っているというだけで、両方共正しい綴りなので、スペルチェッカーには引っかからない)

STEP 1 は、absolute と obsolete がスタックに積まれている状態。
各スタックから POP し、最長共通部分列(longest common subsequence(LCS)) を求める。
LCS は bsol の4文字で、この文字列の前後で POP した文字列を分割する。absolute であれば a-bsol-ute となる。
LCS 以外の部分列をスタックに積む(absolute であれば “a” と “ute”)

gestalt-step1

STEP 2 も、同様に各スタックから POP し、LCS を求める。
POP された “ute” と “ete” の LCS は “te” の2文字。
LCS 以外の部分列をスタックに積む(“ute” であれば “u”)

gestalt-step2

STEP 3 も、同様に各スタックから POP し、LCS を求める。
POP された “u” と “e” の LCS は無いので、スタックには積み直さない。

gestalt-step3

STEP 4 も、同様に各スタックから POP し、LCS を求める。
POP された “a” と “o” の LCS は無いので、スタックには積み直さない。

gestalt-step4

両方のスタックは空になったので、共通文字列の合計を求める。

共通文字列の長さはSTEP 1 の bsol の 4 文字と STEP 2 の “te” の 2 文字を2倍して 2x(4+2)=12文字。
全体の文字列は “absolute” と “obsolete” の 8+8=16文字。

以上から、スコアは「共通文字列の長さ/全体の文字列の長さ = 12/16 = 0.667」 とわかる。

gestalt pattern maching を利用したライブラリ

Python の標準ライブラリには差分操作用の difflib というのがあり、 Ratcliff/Obershelp pattern recognition をベースにした実装がされている。

例えば “appel” が入力されたけど、完全一致するものがない。’ape’, ‘apple’, ‘peach’, ‘puppy’ の中からサジェスト候補となる文字列を探したい場合

>>> from difflib import get_close_matches
>>> get_close_matches('appel', ['ape', 'apple', 'peach', 'puppy'], cutoff=0.4)
['apple', 'ape', 'puppy']

というようにすればよい。
カットオフを厳しくすれば、当然「似ている」と評価される文字列も減ってくる。

>>> get_close_matches('appel', ['ape', 'apple', 'peach', 'puppy'], cutoff=0.6)
['apple', 'ape']

AWS コマンドラインツールの aws-cliこのライブラリを利用して、コマンドを打ち間違えた時に候補(maybe you meant)を表示する。

$ aws s3api put-bucket-gging
usage: aws [options] <command> <subcommand> [parameters]
aws: error: argument operation: Invalid choice, valid choices are:

abort-multipart-upload                   | complete-multipart-upload

... [snip]

Invalid choice: 'put-bucket-gging', maybe you meant:

  * put-bucket-tagging
  * put-bucket-logging
  * get-bucket-tagging

References

Advertisements
Tagged with: , , ,
Posted in algorithm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Archives
%d bloggers like this: