与えられた検索条件に関連する膨大な量の情報に高速検索を実行するのには、コンピューターは向いています。しかし、スペル・チェックをアプリケーションにかけるのに必要な検索能力は、完全なストリング・マッチングの範疇を超えます。この記事では、Soundex や Metaphoneのような音声のマッチング・アルゴリズム、そしてDynamic Programmingアルゴリズムのような（ストリングの類似性に関与する）検索アルゴリズムの歴史にも少し触れます。スペル・チェックに対するこれらのアルゴリズムの長所と短所を両方説明し、最終的な形態(variant)である（特にスペル・チェックのアプリケーションのために作成された）Aspell アルゴリズムを紹介します。

以前からある検索そしてマッチングのアルゴリズムの『いいとこどり』をするAspell アルゴリズムは、Jazzy（Javaプラットフォームのスペル・チェッカーAPI）の基礎をなすフレームワークです。この記事の後半では、JavaフレームワークにてJazzyがAspell アルゴリズムをどのようにして応用するかを紹介します。Jazzyが間違ってスペルされた単語を識別してから修正の候補を提供するのに踏まえるステップを説明します。JazzyがJavaアプリケーションにそのスペル・チェック機能を取り込むのがいかに簡単であるかを、実践的な用例で示すことにより、この記事を締めくくります。

音声のマッチング・アルゴリズム

名字をつづるのは意外と難しいものです。「電話を介して予約を入れるさいに自分の名前がぐちゃぐちゃにされる」などと言うことは、珍しい苗字の持ち主にはよくあることです。例えば、Smith （スミス）とSmyth （スミス）のように発音が同じ場合、ありふれた苗字でも（スペルの小さな違いによる）ミススペルはあり得ます。

特に人名のようなスペルの種類の幅広さは、興味深いスペル・チェックのアルゴリズムの開発に力を入れる理由を提供してきました。最初に、「xのような発音の名前のマッチング」といった問題を解決することを目的とした音声のマッチング・アルゴリズムに注目します。この類のアルゴリズムは、検索データベースや他の参照アプリケーションでかなり普及しています。例えば、家系の歴史を調査する場合には、記録の一部では苗字のスペルが変更されたりスペルが間違えられたりする可能性に備えるためにも、完全なマッチングそして類似するマッチングの両方を回収できるようにするべきです。

上に戻る

Soundex のアルゴリズム

Soundex は、1920年以降の米国人口調査記録全てに索引を付けるのに使用され、家系の歴史を調べるソフトウェアとしては中心的な存在です。Soundex の元々のアルゴリズムの特許を、（「名前のアルファベット構造ではなく音声を基に名前が入力そして分類される」索引を導入する方法を模索していた）Margaret K. Odell氏とRobert C. Russell氏が1918年に取得しております（参考文献を参照）。

本質的に、それぞれの与えられたアルファベットの文字を、その音声のグループを表記する数値コードにマップすることにより、Soundex のアルゴリズムは機能します。このスキームでは、発音が似ていることから『d』や『t』のような文字は同じグループに分類され（実際に、それらの文字は類似する仕組みで発音されています。）、母音はまるきり省略されています。このマッピングを単語まるごとに応用すれば、その単語がいだくphoneticの『キー』の完成です。発音がそっくりな単語同士では同じキーをいだきます。例えば、Smith とSmyth のSoundex キーはどちらもS530です。

中でも最も一般的なSoundex の形態はDonald E. Knuth氏により普及されたThe Art of Computer Programmingです。アルゴリズムのJava実装をリスト1にて見ることができます。リリース1.4以降でしか入手可能でないJavaの通常の表現をそのアルゴリズムが実行していることに注目してください。

                
public class KnuthSoundex implements PhoneticEncoder {
  //                                            ABCDEFGHIJKLMNOPQRSTUVWXYZ
  private static final String SOUNDEX_DIGITS = "01230120022455012623010202";
  public String calculateCode(String string) {
    String word = string.toUpperCase();                                 // 01 ASHCROFT
    word = word.replaceAll("[^A-Z]", ");                               // 02
    if (word.length() == 0) {                                           // 03
      return ";                                                        // 04
    }                                                                   // 05
    char first = word.charAt(0);                                        // 06
    word = first + word.substring(1).replaceAll("[HW]", ");            // 07 ASCROFT
    StringBuffer sndx = new StringBuffer();                             // 08
    for (int i = 0; i < word.length(); i++) {                           // 09
      sndx.append(SOUNDEX_DIGITS.charAt((int) (word.charAt(i) - 'A'))); // 10
    }                                                                   // 11
    word = sndx.toString().replaceAll("(.)\\1+", "$1");                 // 12 026013
    word = first + word.substring(1);                                   // 13 A26013
    word = word.replaceAll("0", ");                                    // 14 A2613
    return (word + "000").substring(0, 4);                              // 15 A261
  }
}

コードに関する注釈

上記のコードは正直素っ気ないので、行ごとに解説します。

• 行番号01から行番号05は、入力を大文字に正規化(normalize)して他の文字を切り落とします。
• 行番号06は、その単語の最初の文字が変更されないことを保証します。
• 行番号07は後に続くHかWの文字を切り落とします。
• 行番号08から行番号11は、その単語にあるそれぞれの文字をその音声コードと入れ替えます。
• 行番号12は隣り合う同一の音声コードを削除します。（母音と異なり、間に挟まれるHやWの文字は同一コード同士の融合を邪魔しません。）
• 行番号06と同様に、行番号13はその単語の最初の文字が変更されていないことを保証します。
• 行番号14は全ての母音を切り落とします。
• 行番号15は、単語を4文字に切り落とすことにより、Soundex を構成します。（場合によっては『0』の文字を含むこともあります。）

本当の意味でアルゴリズムを理解するには、実践的にそれを実行するのが一番です。コードの右側に縦に並ぶものは、入力された名前であるAshcroftで始まる単語の変数の値を追跡します。hを間に挟むにもかかわらずsとcは結合しますので、これはアルゴリズムのテスト・ケースとしてはわかりやすいと言えます。（家系学関連のWebサイトで見受けられるSoundex 実装はこのルールを正しく実装しません。）

スペル・チェック用のSoundex

残念なことに、Soundex はスペル・チェックに向いていません。まず、はっきりと発音が異なる単語が同じsoundexをいだくかも知れません。例えば、White （白）とWood （森林、材木）はどちらも同じsoundex（W300）を割り当てられます。Soundex のアルゴリズムは『同一の』ではなく『類似する』発音を持つ名前を分類するように設計されていますので、これはべつだん驚くべきことでもありません。（様々な方法で発音される名前を電話の交換手が識別する作業を支援するような）一部のアプリケーションでは、この機能は好ましいのかも知れないのですが、（あまりにも多くのマッチングを探し出すので）それはスペル・チェックにおいてはあまり使えません。例えば、algorithmのミススペルである『 algorithum』のマッチングとして、下記に連ねられる単語がサンプル辞書から選ばれます。

alacritous, alacrity, alcheringa, alcoran, algeria, algerian, algerians, algiers, algor, algorism, algorithm, algorithmic, algorithmically, algorithms, alizarin, alizarine, alkoran, alleger, allegers, allegoric, allegorical, allegorically, allegories, allegorist, allegorists, allegorizes, allegory, allegretto, allegrettos, allegro, allegros, allocheiria, allochiria, allocortex, allograft, allograph, allographic, allographs

これよりもはるかに絞り込まれたマッチングをスペル・チェックのアルゴリズムから求めるのが当然の反応であり、同じ単語から派生する様々な品詞（allegoric、allegorical、allegorically）による追加的なマッチング結果を考慮に入れればそれはなおのことです。前述のとおり、Soundex のアルゴリズムはそれぞれのsoundex コードを4文字までに切り捨てますので、（長い単語の場合）尻尾の部分（コード5文字目以降）を無視するがためにマッチングの数を大幅に増やすことになります。そして、悲劇はここで終わりません。

同音異義語の課題

発音の異なる単語が同一のsoundexを持つ可能性もあれば、その逆の状況もあり得ます。同音異義語とは同じ発音を持つ複数の単語を指し、それらは異なるコードを与えられるかも知れません。例えばThompson（T512）とThomson（T525）の場合の p、そしてLeigh （L200）とLee （L000）の場合のghのように、発音されない文字が一部存在するからなのです。似たような傾向として、Carr（C600）のcとKarr（K600）のkのように、単語にある最初の文字が異なっていながらも発音に影響を与えないことも考えられます。Soundex のアルゴリズムは、それぞれの単語にある最初の文字を音声を表記する桁にマッピングしないがために、その問題を自分で引き起こしています。

俗に言う同音異義語の問題は、実を言えば英語と言う言語が（多分他のどの言語よりも）変則的なスペルをともなうから発生するのです。少し手が加えられたSoundex のアルゴリズムの別バージョンはあるにはあるのですが、それらは英語のスペルの法則のみならず法則の例外に関する知識に乏しいのです。この変則性のもたらす結果として、Soundex は英語言語のスペル・チェックに最適だとは言えません。例えば、音声的にスペルを間違えられたlam（L500）に対して、正しい本来のスペルのlamb（子羊）（L510）とは異なるsoundex コードを、Soundex は与えてしまいます。このために、Soundex を基にしたスペル・チェックのアプリケーションは、スペルミスであるlamに対して提案される正しいスペルの候補としてlambを提供しません。このような問題から、Lawrence Phillips 氏はSoundex の代わりとなるMetaphoneを探すにいたったのです。

上に戻る

Metaphone のアルゴリズム

Metaphone のアルゴリズム（1990年に雑誌Computer Language にて最初に発表、参考文献を参照）の裏側にある概念は、Soundex が取り組まない英語の発音に関する通常のルールを明確にコーディングすることです。例えば、Metaphone のアルゴリズムは、単語の最後にあるbがmの文字の後にある場合にはそのbを切り落とす明確なルールを包括します。このルールはlam とlamb が同一のエンコード方式（LM）を所持することを保証し、スペル・チェックのアプリケーションがlamに対する正しい置換候補（lamb）を提供することを可能にします。

Metaphone のアルゴリズムは下記の文字に表記される16の子音のクラス(consonant classes)を使用します。

                
B X S K J T F H L M N P R 0 W Y

『0』は（アルファベット15番目の文字『オー』ではなく）数字のゼロで、『th』の発音を表記します。Soundex のアルゴリズムの場合と同様に、最初の文字は保持されて最終的なコードは4文字に切り詰められます（４文字未満でも文字が単語に無理矢理追加されることはありません）。一般的には、繰り返される文字と母音は（普通の母音もそうですが）切り落とされます。Metaphone のアルゴリズムの大部分は、子音のクラスに文字の組み合わせをマッピングするルールのセットです。Apache Jakarta Commons Codec のプロジェクト（参考文献を参照）にあるMetaphone コードにて例示されるように、Java実装のコードは数百行にものぼります。リスト2に目を通せば、lambと言う単語のコードを調べるためにApache のMetaphone クラスをJUnit のテスト・ケースとして使用した場合に何が起きるかを知ることができます。

                
import junit.framework.TestCase;
import org.apache.commons.codec.language.Metaphone;
public class ApacheMetaphoneTest extends TestCase {
  public void test() {
    Metaphone metaphone = new Metaphone();
      assertEquals("LM", metaphone.encode("lam"));
      assertEquals("LM", metaphone.metaphone("lam"));
      assertEquals(metaphone.encode("lamb"), metaphone.encode("lam"));
      assertTrue(metaphone.isMetaphoneEqual("lamb", "lam"));
  }
}

Metaphone のアルゴリズムは一般的にはSoundexの進化に貢献しますが、そのルールには欠陥がいくつかあります。Metaphone の作成者であるPhillips氏は、例えばBryan （BRYN）とBrian（BRN）が同一のコードをいだくべきだと主張します。Metaphone の（俗に言う）ファジー・マッチングに改良を加える試みを、C/C++ Users Journalの2000年06月号にて発表しました。DoubleMetaphone のアルゴリズムはオリジナルの子音のクラスを少々いじり、全ての単語の最初の母音をAとしてエンコードすることによりSoundex のアルゴリズムとの関連を断ち切ります。より根源的に、（同じ単語であるにもかかわらず）複数の方法で発音される単語のために異なるコードを戻すようにDoubleMetaphone は作成されました。例えば、hegemony はgを柔らかくまたは硬く発音できますので、そのアルゴリズムはHJMN とHKMNの両方を戻します。このような例があるにもかかわらず、Metaphone のアルゴリズムにある単語の大半は、単一のキーしか戻しません。リスト3にて実践されるApacheDoubleMetaphoneクラスをご覧になってください。

                
import junit.framework.TestCase;
import org.apache.commons.codec.language.DoubleMetaphone;
public class ApacheDoubleMetaphoneTest extends TestCase {
  public void test() {
    DoubleMetaphone metaphone = new DoubleMetaphone();
    assertEquals("HJMN", metaphone.encode("hegemony"));
    assertEquals("HJMN", metaphone.doubleMetaphone("hegemony"));
    assertEquals("HJMN", metaphone.doubleMetaphone("hegemony", false));
    assertEquals("HKMN", metaphone.doubleMetaphone("hegemony", true));
  }
}

Soundex とMetaphone の両方ともが音声的なファジー・マッチングを巧妙に解決しますが、スペルミス修正なくしてスペル・チェックのアプリケーションをかたることは許されません。例えば、キーボード上で指がすべってlamb（LM）の代わりにlabm（LBM）と入力すれば、タイプミスが発生します。それぞれの単語が異なる発音をともないますので、音声のマッチング・アルゴリズムはこの類のスペルミスに対してその置換候補を使ってマッチングできません。このような事態に対処するには、ストリング相似性アルゴリズム(string similarity algorithm)をスペル・チェックのアプリケーションは含んでいなくてはなりません。

上に戻る

ストリング相似性アルゴリズム

一度にただ1文字だけを変えるのを繰り返すことにより、1つの単語を次から次へと別の単語に変えるパズルがあるのをご存知でしょうか？例えば、ship（船）は、shop（店）→chop（チョップ）→crop（穀物）を介してcrow（カラス）になります。このゲームは、2つの単語の間をへだてる距離の概念を明確にします。ここで言う距離とは、（一度のステップで1文字だけを変換し、それぞれのステップで辞書に掲載されている（実在する）単語を使用すると言う条件のもと）とある単語を別の単語に変換する際に必要とされるステップの数のことです。ここでは、このことをパズル距離（puzzle distance）と呼ぶことにします。この例にて使われるshipとcrowの間をへだてるパズル距離は、4です。

距離（distance）と言えば我々はどうしても空間に存在する2点間の物理的な測定を連想するのですが、数学者はより総体的に距離（metric）を定義します。この定義は距離の概念を別のアプリケーションにて活用できます。ここで大事なのは、2つの文字ストリング（または単語）の間の距離です。タイプミスが発生した場合、その間違った単語に相応しくて（ここで言う距離の定義に基づいて）『近い』単語を検索すべきです。どのような距離（distance、metric）も、距離として認定されるには（例えば、負の数字があり得ないなどのように）幾つかの性質の条件を満たさなくてはなりません。

文字列の比較は多くの側面を持ち（参考文献を参照）、良質なスペル修正へと導く距離の概念を見つけるのが目的達成の秘訣と言えます。上記にて定義されるパズル距離は少なくともひとつの（タイプミスされた単語が正しい単語と1文字だけしか違わないとは限らないと言う）ごもっともな理由から不適切なのです。例えば、タイプミスされた単語puzzelを正しくスペルされた英単語（puzzle）へと導く『踏み台』が用意されているとは言えません。それでも、幸運なことにスペル・チェックに適したmetric（距離）が既に編み出されています。

上に戻る

Dynamic Programming のアルゴリズム

Dynamic Programming のアルゴリズムは、ソース・ワードからターゲット・ワードへの全ての異なる道を考慮して2点間の最小コスト（最短距離）を探し当てる、本質的に力技の手法です。Dynamic Programming のアルゴリズムの特殊な実装であるレーベンシュタイン距離（Levenshtein distance）は、ソース・ワードであるxをターゲット・ワードであるyに変換する3種類のオペレーションを可能にします。

• xにある1文字をyにある1文字に置換
• xにある1文字を削除
• yに1文字を挿入

それぞれのオペレーションにはコストというものがあり、ワードxをワードyに変換する場合の最小コストが総合距離なのです。これらのオペレーションでのキー入力のエラーを解釈次第ではタイプミスとも定義できますので、これらのオペレーションを基にしたアルゴリズムがスペル修正にてうまく機能するのは直感的に理解できます。実際に、レーベンシュタイン距離は編集距離(edit distance)としても知られています。例えば、wrongと言う単語をwromg（nのキーの代わりにmのキーを押す）と入力したら、それは入力エラー(substitution error)です。もしもwromng（mキーとnキーを両方押す）と入力したら、それは削除エラー(deletion error)です。もしもwrog（nキーを押し忘れる）と入力すれば、それは挿入エラー(insertion error)です

距離を計算

ソース・ワードの文字に対応する列、そしてターゲット・ワードの文字に対応する行をともなうグリッドを作成するのが、Dynamic Programming のアルゴリズムを理解する最良の手段です。座標(i, j)にあるセルは、ソース・ワードにある最初のi文字とターゲット・ワードにある最初のj文字の間をへだてる最短距離を表記します。

レーベンシュタイン距離の場合、削除と挿入のコストは1です。文字が異なれば置換のコストは1ですが、そうでなければ（文字が同じであれば）コストは0です。アルゴリズムを開始するには、まず（空のソース・ワードに該当する）最初の列を埋めます。つまり、連ねられる挿入のコストは0, 1, 2の順番でj（ターゲット・ワードの文字数）までです。それと同様に、最初の列は空のターゲット・ワードに該当し、0, 1, 2 …i（ソース・ワードの文字数）の順番で削除のコストを書き連ねます。pzzelをpuzzleに変換する例を取り上げるのであれば、図1にて示されるグリッドが出来上がります。

上、左、そして左上にある3つの近隣のセルを考慮に入れて、空いているセルに値を埋めます。図2で説明しています。

この例から得られた結果としてのグリッドを図3に示します。グリッドの最も右下にあるセルのコストは3であり、それこそがpzzelとpuzzleの間のレーベンシュタイン距離なのです。

レーベンシュタイン・アルゴリズムの特性

おまけとして、レーベンシュタイン・アルゴリズムは変換を構成するアライメント(alignments)とも呼ばれる一連のオペレーションを提供します。一組の単語（ソース・ワードとターゲット・ワード）が複数のアライメントを持つのはよくあることです。図に描かれてある最も左上のセルから最も右下のセルへの最低コストのルートにアライメントは該当します。例えば、リスト4にて示される（図3にて赤い矢印として描かれる）アライメントは、文字ごとに読めば下記に連ねられるオペレーションの羅列となります。

• pをp に置換（コスト0）
• uを挿入（コスト1）
• zをz に置換（コスト0）
• zをz に置換（コスト0）
• lを挿入（コスト1）
• eをe に置換（コスト0）
• lを削除（コスト1）

                
p-zz-el
puzzle-

レーベンシュタイン・アルゴリズムのJava実装

簡素で例証となるレーベンシュタイン・アルゴリズムのJava実装はリスト5にて示されています。LevenshteinDistanceMetric クラスは、Apache Jakarta Commons プロジェクトからのStringUtils クラスと類似します。ストレージ要件はO(mn)（ mとnはそれぞれソース・ワードとターゲット・ワードの長さ）でありますので、これら双方の実装の制限はそれらが大型のストリングに合わせて調節しないことです。もしも（よくあることですが）アライメントではなく距離のみを計算したいのであれば、前の列さえ解ればその次を計算できますので、ストレージ要件をO(n)に縮小するのが手っ取り早いです。Apache のバージョンにて修正が提案されていますが（参考文献を参照）、この記事が作成された時点（バージョン2.0）ではまだ具現化されておりません。

レーベンシュタイン・アルゴリズムでの実行時間は常にO(mn)であることに注目してください。その結果、巨大な辞書にてミススペルに対する最も近いマッチングを探すにはこのアルゴリズムはあまりにも遅いと言えます。

                
public class LevenshteinDistanceMetric implements SequenceMetric {
  /**
   * Calculates the distance between Strings x and y using the
   * <b>Dynamic Programming</b> algorithm.
   */
  public final int distance(String x, String y) {
    int m = x.length();
    int n = y.length();
    int[][] T = new int[m + 1][n + 1];
    T[0][0] = 0;
    for (int j = 0; j < n; j++) {
      T[0][j + 1] = T[0][j] + ins(y, j);
    }
    for (int i = 0; i < m; i++) {
      T[i + 1][0] = T[i][0] + del(x, i);
      for (int j = 0; j < n; j++) {
        T[i + 1][j + 1] =  min(
            T[i][j] + sub(x, i, y, j),
            T[i][j + 1] + del(x, i),
            T[i + 1][j] + ins(y, j)
        );
      }
    }
    return T[m][n];
  }
  private int sub(String x, int xi, String y, int yi) {
    return x.charAt(xi) == y.charAt(yi) ? 0 : 1;
  }
  private int ins(String x, int xi) {
    return 1;
  }
  private int del(String x, int xi) {
    return 1;
  }
  private int min(int a, int b, int c) {
    return Math.min(Math.min(a, b), c);
  }
}

上に戻る

Jazzy登場

これまでに、スペル・チェックへの2種類のアプローチ（音声マッチングと文字列比較）を考慮してきました。しかしどちらもが単独では完全な解決法ではありませんので、それらを結合するアルゴリズムを作成するにいたりました。以下はGNU Aspell のマニュアルからの引用です。

spellを裏から支える魔力は、Lawrence Philips 氏の優秀なmetaphone アルゴリズムとIspellの（ミススペルされた単語に近い別の単語の修正候補をも検索する）ニアミス・ストラテジー(near miss strategy)を組み合わせることであり、それはスペースまたはハイフンを挿入し、隣り合う2つの文字を交換し、文字を1つ変更し、文字を1つ削除し、そして文字を1つ追加したりします。

Jazzyは、GPL/LGPLに登録されたJavaを基にしたスペル・チェックAPIであり、それは　元々C++で書き込まれたAspellアルゴリズムをベースにしています。

Aspell アルゴリズムとJazzy

もしもスペル・チェックの対象となっている単語が辞書になければ、Aspell アルゴリズムはその単語がミススペルされていると想定します。この場合、アルゴリズムは下記のステップを使い、提案される修正候補のランクされたリストを作成します。

1. ミススペルされた単語に近い音声マッチングを追加: ミススペルされた単語と同じ音声コードを持ち、ミススペルされた単語からの編集距離が与えられたしきい値よりも小さい辞書単語を全て追加します。
2. ミススペルされた単語に近い別の単語（ニアミス単語）の音声マッチングを追加: ミススペルされた単語から編集オペレーション１回分異なる別の単語（ニアミス単語）の音声コードを探します。それらニアミス単語の音声コード同じ音声コードを持ち、ニアミス単語からの編集距離が与えられたしきい値よりも小さい辞書単語を全て追加します。
3. 最良の推測: もしも提案が何もなければ、ミススペルされた単語と同じ発音をいだき、ミススペルされた単語から最小の編集距離をへだてる、全ての辞書単語を追加します。
4. ソート（分類）: 編集距離で単語をソートして、それぞれのステップで発見した単語をまとめて保管します。

Aspell アルゴリズムの強みは、単語のレベルと音声コードのレベル両方にて編集距離を使用する手法にあります。実際には、ミススペルされた単語に対する良い提案を提供するには、これは十分な曖昧さを供給します。

編集距離に関する注釈

Jazzy にて使用される編集距離は、前述されたレーベンシュタイン距離の定義とは異なります。置換、削除、そして挿入だけではなく、Jazzyは隣り合う文字を交換したり大文字小文字を変えるオペレーションをも取り入れます。オペレーションのコストは構成可能です。Metaphoneのようなテーブルを使って変換を定義する方法である音声変換ルールのファイル（参考文献を参照）を使用するのは可能なのですが、デフォルトの音声エンコード方式はMetaphoneです。テーブル主導型のアプローチは、Jazzyをベースにしたスペル・チェッカーが他の言語をサポートするように構成することを簡単にします。

上に戻る

スペル・チェッカーを作成

ここから先では、Jazzy APIを使用してスペル・チェッカーを実際に作成するステップを説明することに専念します。いかにしてJazzyを使ってJava スペル・チェッカーを作成するかを、リスト6にて示します。

                
import java.io.BufferedReader;
import java.io.File;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.List;
import com.swabunga.spell.engine.SpellDictionary;
import com.swabunga.spell.engine.SpellDictionaryHashMap;
import com.swabunga.spell.event.SpellCheckEvent;
import com.swabunga.spell.event.SpellCheckListener;
import com.swabunga.spell.event.SpellChecker;
import com.swabunga.spell.event.StringWordTokenizer;
public class Suggest {
  public static class SuggestionListener implements SpellCheckListener {
    public void spellingError(SpellCheckEvent event) {
      System.out.println("Misspelling: " + event.getInvalidWord());
      List suggestions = event.getSuggestions();
      if (suggestions.isEmpty()) {
        System.out.println("No suggestions found.");
      } else {
        System.out.print("Suggestions: ");
        for (Iterator i = suggestions.iterator(); i.hasNext();) {
          System.out.print(i.next());
          if (i.hasNext()) {
            System.out.print(", ");
          }
        }
        System.out.println();
      }
    }
  }
  public static void main(String[] args) throws Exception {
    if (args.length < 1) {
      System.err.println("Usage: Suggest <dictionary file>");
      System.exit(1);
    }
    SpellDictionary dictionary = new SpellDictionaryHashMap(new File(args[0]));
    SpellChecker spellChecker = new SpellChecker(dictionary);
    spellChecker.addSpellCheckListener(new SuggestionListener());
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    while (true) {
      System.out.print("Enter line to spell check (return to exit): ");
      String line = in.readLine();
      if (line.length() == 0) {
        break;
      }
      spellChecker.checkSpelling(new StringWordTokenizer(line));
    }
  }
}

main()メソッドは、コマンド行にて指定されたファイルからSpellDictionary を作成します。SpellDictionaryHashMap 実装は（速いのはいいのですが大型の辞書に適しているとは必ずしも言い切れない）メモリーに単語を保管します。（メモリー重視のアプリケーションには、ディスク・ベースの実装が提供されます。）標準入力から入力の行をフィードされる前に、（SpellChecker オブジェクトとともに登録された）SpellCheckListener を持つSpellChecker オブジェクトを構成するために、SpellDictionary が使用されます。スペル・チェッカーが典型的に組み込まれたユーザー主導型のアプリケーションに、イベント・ベースの設計はしっくりとはまります。この場合、listener（SuggestionListener）は、SpellCheckEventを受信するたびに単にミススペルされた単語そして標準出力への提案リストを書き出します。リスト7にてサンプル実行を示します。

                
Enter line to spell check (return to exit): choklut biskit
Misspelling: choklut
Suggestions: chocolate
Misspelling: biskit
Suggestions: biscuit
Enter line to spell check (return to exit):

この例はとても簡素ですが、より凝ったアプリケーションはJazzyがサポートするユーザー辞書管理を使え、新規の単語を辞書に追加したり、単語を無視したり、繰り返しミススペルされる単語を選ばれた修正単語に自動的に置換したりなど、さまざまなタスクを実行できます。詳細については、SpellCheckEvent （参考文献を参照）のAPI 文書をご覧になってください。

上に戻る

まとめ

この記事が作成された時点では、Jazzy API はまだバージョン0.5のアルファ版です。比較的まだ新しいAPIとして、Jazzyには進化と拡張の余地があります。まず手始めに、Jazzyはその親戚とも言えるAspellに加えられた改良点をより正確に反映できます。より大袈裟に言えば、Jazzyとは、単語の単純なリストと言うよりも、（自然言語処理の機能の一部を使用してコンテキストを認識し文法を認識するスペル・チェッカーのプロトタイプ作成の）理想的なフレームワークだと言えます

実情においては、Javaプラットフォームにてスペル・チェックのソフトウェアを開発するうえでは、Jazzyは相対的に基本に忠実でありながらも手堅いAPIです。Jazzyはオープン・ソースですので、その現在進行中の開発に誰もが貢献できます。APIはフレームワークとして活用され、組織内でのアプリケーション開発にも拡張されたりもします。Javaプラットフォームの新型のスペル・チェッカーAPIであるJazzyのみならず、この記事にて考察されたアルゴリズムについてより多くを学ぶのでしたら、参考文献の章をご覧になってください。

上に戻る

ダウンロード

ダウンロード形式について

参考文献

• この記事の最初と最後にあるCodeアイコンをクリックして、この記事にて使用されるソース・コードをダウンロードしましょう。
  
  
• このEclipseのプラグインは、Java、JavaScript、Java プロパティー・ファイル、XML、HTML、JSP、そしてPHPにスペル・チェックの機能を提供するためにJazzy を使用します。
  
  
• Margaret K. Odell 氏とRobert C. Russell 氏によるオリジナルのSoundex アルゴリズムは、1918年に特許を与えられました。
  
  
• Donald E. Knuth 氏による「The Art of Computer Programming,Volume 3, Sorting and Searching」（Addison-Wesley、1998年）は、Soundex アルゴリズムの権威ある記述を記載しています。
  
  
• Lawrence Philips 氏による「Hanging on the Metaphone」（Computer Language、1990年12月）にて、Metaphone アルゴリズムに関する最初の記述が掲載されました。
  
  
• 「The Double Metaphone Search Algorithm」（C/C++ Users Journal、2000年06月）の記事にて、Lawrence Philips 氏によるMetaphone アルゴリズムの改良版が発表されました。
  
  
• David Crystal氏による「The Cambridge Encyclopedia of Language」（Cambridge University Press、1997年）は、世界の言語に関する事実を知るうえで便利な虎の巻です。
  
  
• Apache Jakarta Commons LangプロジェクトのChas Emerick 氏は、（この記事が作成された時点ではまだバージョン2.0に修正が加えられていないのにもかかわらず）かなり巨大なストリングにレーベンシュタイン距離を使用する際に発生する問題の解決法を提案しました。
  
  
• レーベンシュタイン距離に関する数学的な詳細、そしてそれと関連するストリングの距離のmetricに関しては、Christian Charras 氏とThierry Lecroq氏による「Sequence comparison」を参照してください。
  
  
• Aspell のアルゴリズムへの完全なガイドでしたら、Aspellのホームページを訪れてみてください。
  
  
• 優良なWord Listを選ぶのは、良質のスペル・チェックのアルゴリズムを使用するのと同様に重要です。
  
  
• alphaWorksによるDictionary and Thesaurus API for Java を品定めするのも面白いかも知れません。
  
  
• WordNet は、英語の名詞、動詞、形容詞、そして副詞を（それぞれが字句的な概念を表記する）同義語のセットとしてまとめる電子字句データベースです。
  
  
• 「Efficient text searching in Java」（developerWorks、1999年04月）は、Unicodeでのテキスト検索アルゴリズムに注目します。
  
  
• 「Finding text boundaries in Java」（developerWorks、1999年07月）は、多種にわたる言語にあるテキストの境界線を探すうえでの難解さを考察します。
  
  
• Javaのオープン・ソースのスペル・チェッカーであるJazzyをダウンロードしましょう。
  
  
• フリーなオープン・ソースのスペル・チェッカーであるGNU Aspellをダウンロードしましょう。
  
  
• Soundex、Metaphone、そしてDouble Metaphoneのオープン・ソース実装用のApache Jakarta Commons Codecをダウンロードしましょう。
  
  
• レーベンシュタイン距離のオープン・ソース実装のためにあるApache Jakarta Commons Lang をダウンロードしましょう。
  
  
• IBMdeveloperWorks にあるJava technology関連のページにて、Javaプログラミングに関連するあらゆる見解の記事を探せます。
  
  
• Javaに関連する数百ものタイトルを含む技術書物の包括的なリストのあるDeveloper Bookstoreを訪れてみて下さい。
  
  

著者について

この記事を評価する

コメント

上に戻る

目次

• 音声のマッチング・アルゴリズム
• Soundex のアルゴリズム
• Metaphone のアルゴリズム
• ストリング相似性アルゴリズム
• Dynamic Programming のアルゴリズム
• Jazzy登場
• スペル・チェッカーを作成
• まとめ
• ダウンロード
• 参考文献
• 著者について
• コメント