divergence_meterというgemを作った - Webアプリエンジニア養成読本 Advent Calendar 2014 24日目

Webアプリエンジニア養成読本 Advent Calendar 2014 - Qiita の24日目です。12/24の23:40の時点で書き始めているので許してニャン

Webアプリエンジニア養成読本[しくみ、開発、環境構築・運用…全体像を最新知識で最初から! ] (Software Design plus)

このアドベントカレンダーで Gemライブラリ作ってこ！ - すがブロ という話を書きました。 その続きというわけではありませんが、少し前にGemライブラリを作成したのでその話をしたいと思います。

何を作ったのか

レーベンシュタイン距離 - Wikipedia という文字同士の編集距離を調べるアルゴリズムを実装したのでした。 例えば、aaa と aab は1文字変更すると同じ文字列を作成できるので、編集距離が1ということになり、 比較的似ている文字列である というのがわかります。

ついでに、編集距離を調べるだけではなく、調べたい単語と、辞書データ（単語群）を引数で渡すと、単語に最も近い辞書データの単語を探してくるという「もしかして？」機能も作ってみました。

$ gem i divergence_meter --no-document
Fetching: divergence_meter-1.0.1.gem (100%)
Successfully installed divergence_meter-1.0.1
1 gem installed
$ pry
[1] pry(main)> require 'divergence_meter'
=> true
[2] pry(main)> DivergenceMeter.もしかして('__sand__', %w(send __send__ hoge))
=> "__send__"

実装自体は上記のWikipediaに乗っている擬似コードをRubyに読み替えるだけなので大して難しくありません。それどころか、実装した後で気がついたのですが

編集距離が近いメソッドを勝手に呼ぶ - hitode909の日記

とか

編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー

とかで語られていて、もう何周遅れのネタだったんだ、という感じです。テストケースの材料としていくらか参考にさせていただきました。

あ、ちなみにこのアルゴリズムを実装した目的は、この文章のような長文の文字列から誤字脱字を見つけられないかなと思って作ってみたのでした。

すでにあるもの作ってどうするの問題

自分にとっては、このアルゴリズムを実装するのは初めての経験だったので良いのです。いわゆる車輪の再発明ってヤツですが、作る上で学びがあるなら良いじゃないか〜という感じですね。あと、個人的なニーズとして、Gemライブラリになっていると都合が良かったというのもあります*1。

すでにあるものを作ってどうするのかという葛藤、あるにはありますが、その分野で一旗揚げるような野心がある人は別として、自分の経験のために作っても良いと思いますのでカジュアルに作ってみるのが良いのかな、と思います。

ちなみにGemライブラリの名前の由来は

編集距離を世界線変動率*2と置き換えてみたら面白いかなーという思った次第です。

書かなくてはならない宣伝

Webアプリエンジニア養成読本[しくみ、開発、環境構築・運用…全体像を最新知識で最初から! ] (Software Design plus)

この本を読んだあと、何かコードを書いてみたいけどイマイチ書くものが思いつかないよ！　という方は、上記のレーベンシュタイン距離のような簡単なアルゴリズムを自分でRubyのコードに翻訳してみる、というのをやってみると意外と面白いかもしれませんね。

enjoy!

*1:当初GitHubにだけ公開してたのですが、ちょっと事情があってRubyGemsにもアップしました

*2:シュタインズゲートでググってみてください