ようこそ!浜村拓夫の世界へ

    ブログ内検索

    最近の記事

    ブックマーク数の多い記事

    Blog Translation

    Powered By FC2ブログ

    Powered By FC2ブログ
    ブログやるならFC2ブログ


    FC2ブログ LOGIN

    with Ajax Amazon

    レーベンシュタイン距離

    このエントリーを含むはてなブックマーク はてなブックマーク - レーベンシュタイン距離 あとで読む
    アナグラムの解析で、「レーベンシュタイン距離」という概念、用語があることを知りました。(メモ)

    レーベンシュタイン距離 - Wikipedia

    レーベンシュタイン距離は、二つの文字列がどの程度異なっているかを示す距離である編集距離の一種類である。
    具体的には、文字の挿入や削除、置換によって、一つの文字列を別の文字列に変形するのに必要な手順の最小回数として与えられる。
    名称は、1965年にこれを考案したロシアの学者ウラジミール・レーベンシュタインにちなむ。

    スペルチェッカー等において、二つの文字列がどの程度に類似しているかを具体的な値として示す一つの方法である。
    さらなる応用として注目を浴びつつあるのがバイオインフォマティクス分野での活用であり、DNA配列同士の類似性を判断するために応用されている。
    これはDNAが挿入・欠失・置換の3様式によって変化していくことの反映である。
    異なる生物種が持つ同様の遺伝子を同定したり、またそれらの距離を測ることで種が分岐してから経過した時間を推定するなどを実現している。

    Bitapアルゴリズムが、レーベンシュタイン距離がある値以下のパターンを検出するアルゴリズムとして知られている。agrepという実装がある。



    Vladimir Levenshtein
    Dr. Vladimir Levenshtein

    情報検索の基礎
    Christopher D.Manning / Prabhakar Raghavan / Hinrich Schutze
    共立出版
    2012-06-23
    ¥ 8,640

    関連記事

    コメント

    コメントの投稿


    管理者にだけ表示を許可する

    トラックバック

    トラックバックURL:
    http://hamamuratakuo.blog61.fc2.com/tb.php/1095-6b2eb17e

    FC2Ad