レーベンシュタイン距離(編集距離)を完全に理解した！

こんにちはyapattaです。

AOJ(AIZU ONLINE JUDGE)のレーベンシュタイン距離の問題を解くことができなかったから、理解するために記事を書いた。プログラミングをやってない人でも理解できる記事を書きたい。

1)レーベンシュタイン距離(編集距離)とは？

レーベンシュタイン距離とは、とりあえず２つの文字列がどのぐらい違っている文字列か表す指標であると理解してもらえるといい。

文字列Aの中の1文字を、置換、挿入、削除を繰り返しすことで、一方の文字列Aをもう一方の文字列Bに変形する。この繰り返しの最小回数をレーベンシュタイン距離という。詳しくは以下↓

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

2)どんな問題?

まずこんな問題

Edit Distance (Levenshtein Distance) | Aizu Online Judge

ある文字列を２つ入力して、その２つの文字列のレーベンシュタイン距離を出力するという問題

3)実装方法

レーベンシュタイン距離にある、以下の２つの性質を用いて漸化式を立てることで、レーベンシュタイン距離を求められる。

注)LP(x, y)は文字列xとyのレーベンシュタイン距離を指す。

性質1) 文字列xの長さがS、文字列yが空文字列(長さが0)のとき、LP(x, y) = S

xの文字をS回削除したら、xが空文字列になるため、LP(x, y) = Sになることがわかると思う。

具体的に考えてみよう。 x = "apple"(xの長さは5)、y = ""(yの長さは0)とする。このとき、xの文字を5回削除したら、xはyと等しくなるから確かに、LP(x, y) = 5

ちなみに、xが空文字列、yが長さSの文字列であったとしても、xにS回文字を挿入したら、yと同じ文字列になるため、LP(x, y) = S

性質2) LP(x,y)は漸化式によってわかる

 x = "book" y = "desk"としたとき

(1)最後の文字が等しいときについて

LP("book", "desk") = LP("boo", "des")

これは、x[3](xの4文字目)とy[3]](yの4文字目)が両方'k'で等しいため、最後の文字kがなくても編集距離は同じことによる

(2)削除について

LP("boo", "des") = LP("bo", "des") + 1

"boo"から'o'を削除したものが"bo"となるから、確かに、

LP("boo", "des") = LP("bo", "des") + 1が成り立つ

(3)挿入について

LP("boo", "des") = LP("boo", "de") + 1

"boo"に一文字sを挿入したとき、LP("boo", "des") = LP("boos", "des") + 1

ここで(1)より、LP("boos", "des") = LP("boo", "de")となるから、

確かに、LP("boo", "des") = LP("boo", "de") + 1 が成り立つ

(4)置換について

LP("boo", "des") = LP("bo", "de") + 1

"boo"の3文字目の'o'をsに置換したところ、LP("boo", "des") = LP("bos", "des") + 1

ここで(1)より、LP("bos", "des") = LP("bo", "de")となるから、

確かに、LP("boo", "des") = LP("bo", "de") + 1 が成り立つ

(1)(2)(3)(4)の漸化式を用いて、最小のレーベンシュタイン距離を求めたいから、

配列LPを確保して、任意のLP[j][k](j >= 1 ∧  k >= 1)について、最後の文字が等しいかで場合分けして、

if xのj文字目 == yのj文字目
LP[j][k] = min(LP[j-1][k]+1, LP[j][k-1]+1, LP[j-1][k-1])

if xのj文字目 != yのj文字目
LP[j][k] = min(LP[j-1][k]+1, LP[j][k-1]+1, LP[j-1][k-1]+1)

としたら求まるね!

注) ここでLP[j][k]はxのj文字目までの文字列と、yのk文字目までの文字列のレーベンシュタイン距離を表す。

じゃあ実際に実装してみよう

4)実装方法をもとにしてできたコード

#include <iostream>
#include <string>
using namespace std;
int LP[1005][1005]={};

int main() {
  int j,k;
  string x,y;
  cin >> x >> y;
  for(j=1;j<=x.size();j++) LP[j][0] = j;
  for(k=1;k<=y.size();k++) LP[0][k] = k;

  //aをbに近づけたい!
  for(j=1;j<=x.size();j++) {
    for(k=1;k<=y.size();k++) {
      //a[j]を削除するか、a[j+1]にb[k]と同じ文字を挿入するか
      //上記２つの行為の回数で最小な方を採用
      int m = min(LP[j-1][k]+1, LP[j][k-1]+1);
      if(x[j-1] == y[k-1]) {
        //最後の文字が同じだから最後の文字がなくても編集距離は同じ
        m = min(m,LP[j-1][k-1]);
        LP[j][k] = m;
      }else {
        //最後の文字を置換する
        m = min(m,LP[j-1][k-1]+1);
        LP[j][k] = m;
      }
    }
  }
  cout << LP[x.size()][y.size()] << endl;
  return 0;
}

 

5)レーベンシュタイン距離の実用例(個人的見解)

類似内容の発見に使えそうだよね。

文書作成ソフトとかで、"play"じゃなくて間違って"plai"と打ったときに、レーベンシュタイン距離が近いため、"play"と正しい候補が出てくる的なことを個人的にイメージした。本当にレーベンシュタイン距離が使われていたらうれしいな。

ということでまた

外国語上達法 書評

こんばんは、yapattaです

Twitterの書評を書き直した

あまりにも個人的だったので

内容と感想を書いた

本についての内容はざっくりだいぶ古い本であるため書評も多く、調べたら内容がわかるから

本のリンクは↓

外国語上達法 (岩波新書 黄版 329)

内容

良い語学教師の条件として絶対的に生徒に語学の実力を疑われない

とか、発音が綺麗とか

同じ単語を何回も繰り返している学習書とかオススメだとか。記憶に定着しやすいからね。

あとは、学習書を作る大変さについて。最初の3課あたりは、語彙にも文法にも制限が多いににも関わらず、学習者に学習をやめさせないように面白い内容にしなければならない。思っている以上に大変だよ！

ここからは個人的感想

言語を学習してて思うことは、ただ教えられたものをそのまま受け入れるだけじゃ、つまらない。このフレーズを知ったらこういう場面で使える！とか、日本語の分法と比較して表現の仕方がまったく違う、すげえ！とか、能動的に学習していった方が、楽しいよな。

だから、良い先生の条件として付け足しで、生徒の能動性を弱めない先生が良い先生の条件なのかと。

生徒の質問に真摯に向き合うとか。感動を共有するとか。なかなかできる先生は少ない。

この点、私の大学のロシア語の先生は良い先生の条件をすべて満たしてるなあ、と改めて尊敬の念を抱きました。

今年日記

今年何した書く

来年の自分のために役たって欲しい

4月

大学入学。大学生になったらプログラミング頑張ろうとか思ってた。ラグビーをやってたこともありタックルが好きだったため、レスリング部の体験に行ったら、レスリングが楽しくて4月中は毎日レスリング部の体験練習に行ってた。しかし、プログラミングを勉強する時間が取れなそうなので結局入らなかった。

5月

Ruby On Railsやdockerの勉強を始めた。競技プログラミングも始めた。Rails Tutorialを読み始めた。競プロのため、c++を使い始めた。特に記憶がない。

6月

Railsチュートリアルを読んでた。adobeXDでアプリデザインを作れるようになったようになった。ノンデザイナーズデザインブックとか読んだ。特に記憶がない。

7月

Railsチュートリアルを読み切った。友達と

Railsのスマホ対応のアプリを作った。(https://github.com/yuziroppe/sophistock )

この時まだ、javascriptというものを知らなかった。

期末試験で落単というのはどういうものか理解した

8月

ロシア語の数字すらわかんない状態だったが、ノリで申し込み、ロシアのアストラハンに一ヶ月ほど語学留学した。ロシアが好きになった。

ロシア語のモチベがくっそ上がった。

9月

プログラマとして、インターンを始めた。

PHPもJSもわかんないから大変だった。けど、自分の成長を感じ楽しかった。取引の場を見せてもらったり、いろんな社会的マナーを教えてもらった。

10月

主な記憶がインターン。初リリースノートを出した。ロシア語ガチ勢になったが、大学でロシア語以外の勉強をした記憶がない。

11月

主な記憶がインターン。中間試験で数学の点数が半分を切った。ロシア語の授業を週4で受けるようになった。大学での勉強のモチベがロシア語以外特に低かった。バタバタしている時期だった。

12月

これから書こう。

Я кончаюを超まじめにやさしく文法分析

こんにちは

yappataです

今日はとんでもないロシア語フレーズ講座Part1

女性のみなさんは是非ともブラウザバック推奨！！

絶対だぞ！！

見て、後悔するなよ？見て惚れるなよ？？

では、本当に終わったのかは別として、選定が終わったことで、

みなは、精子を出す瞬間、｢イクゥ！！｣をロシア語でどう表現するかご存じだろうか？

知ってたら、ロシア語通ですね(´･ω･｀)

答えは、

｢Я кончаю(や かんちゃーゆ)｣！！

あっ、タイトル見たらわかるか、、

今回、このフレーズを超まじめに文法分析することを目標とする

まず、｢я｣ついて、

これは、英語で言う「I」である。

｢私｣を表す言葉の主格

ちなみにロシア語には格が5つあって、｢私｣を表す言葉も、主格(~は)、生格(~の)、与格(~に)、対格(~を)、造格(~として)、前置格(表現不能)によって意味が変わるのだ。

なかなか覚えるのだけでも大変だ、、、

次に｢кончаю｣について、

すごい簡単に言うと｢кончаю｣は｢終わる｣という意味である

でも、それだけで終わらせたら、非常につまらない

より詳細に話そう

ぜひ最後まで読んで欲しい

｢кончаю｣は、不完了体動詞｢кончать｣の現在形一人称変化である(ロシア語は人称によって、動詞の形が変化する)

ロシア語を勉強したことない人は、不完了体動詞、完了体動詞って言葉に聞き慣れないだろう。

まあ、文字の通りである。不完了体動詞は動作が完了していないとき、完了体動詞は動作が完了したときに用いる。

ここで、｢кончать｣は不完了体動詞である。

勘の鋭い者は、以下のように不思議に思うかも知れない。

｢終わる｣っていう動詞は完了したことを表すのではないか？

｢終わる｣で不完了とはどういうことか？

不思議に思うのはもっともだ

まあ、読んでいけばわかるさ(フフフ、、)

｢終わる｣の不完了状態を、素直に日本語に訳すと、｢終わりつつある｣である

この｢終わりつつある｣ってのが、精子を出しているけど、出し終わってないあの臨場感をもろに出しているのだ！！！

ロシア語ってスゲぇ

2語で表すこの臨場感

また、他に｢終わる｣を表す言葉、｢закончать｣を使っても、｢行くぅ！｣の意味にならないから注意しよう

｢закончать｣は、最後までやり遂げる、という意味であるため、微妙にニュアンスが違うからだ

余談だが、私がなぜこのフレーズを覚えたかというと、ロシアに滞在中、ロシア語の授業が終わったときに、｢I finished｣の意味で、｢Я кончаю｣といったところ、ロシア人の友達が口を押さえてきて、不思議に思って、後日意味を調べたところ、真の意味をしってしまった。ということがあった。

ああ、ロシア語っておもしろい！！

ってことで、また

眼精疲労の正体

久しぶりです

yappattaです

今日は11/11、ポッキーの日だけど、ポッキーとまったく関係ない話について!

最近の苦労話について

九月ごろからコーディングの仕事をはじめたのだが、目がものすごく疲れる

何だろう、パソコンの見過ぎか

そう思って、仕事のない土日に目を休めることで、何とか騙し騙しコーディングをしていた

しかし、おかしい

焦点が合わない感じ

近くを見ても遠くを見ても焦点が合わない

文章を読んでも、頭に文字が入ってこない

起きて、数時間たつと目に疲労がたまってきて、頭もうまく動かない。相手の話が入ってこない。

コーディングのときは何とか根性で頑張れるが、仕事が終わり、家に帰った途端、何もやる気が起きなくてうなだれる日々が続いた

生活に支障をきたしてるし、このままじゃまずい、、

って思って、重い腰を上げて眼科に行くことにした

そしたら、結膜炎にかかっていることと、自分の乱視が急激に進行していることがわかった

どうりで、物の焦点が合わないわけだ

確か、-1.75ぐらいの度

矯正しないといけないぐらい強い乱視になってた

うーん、怖い

どうして急に度が進行したかわからないが、目の疲れの原因がわかってよかった

何を伝えたいかというと、

目の疲労とかたまっていたら、自己解決しようとするんじゃなくて、素直に早めに病院に行った方が良かったりするってこと

一ヶ月ぐらい、目の疲労で悩んでいたから、よく実感できた

ではまた

そういえば夏休みロシアに行ってきた Part1

アストラハン大学に夏の間、1ヶ月語学留学兼ホームステイをしてきた。

なかなか珍しい経験だと思うので、記録に残したい。

今回乗った飛行機

 

1.動機

 私は大学一年生である。第二外国語(週2)としてロシア語を、四ヶ月ほど勉強してきた。

せっかく二外をやってるんだったら、使った方が得だし、二外のモチベを上げるかぐらいの気持ちでロシア留学に申し込んだ。

 

あとは、人生発の海外で普通の国に行くんじゃつまらないという理由と(ロシアに失礼)、夏休みが長くてやることがなさそうだったからという理由も。(まともにサークルをやってない)

 

2.申し込み

これが大変だった。現地の大学の日本語が話せるロシア人の先生に直接メールを送って申し込みのやりとりをした。(大学のサポートはない！)

ロシアに行くまでは全部自分でやらなければならない！留学エージェントなどない！

 

授業料はユーロのみでの送金だし(ユーロ送金できる銀行は限られてる)、送金してもあっちの大学から1週間ほど返信がこないしと、なかなか先が思いやられた。

また、ビザ申請書が渡航1週間前ギリギリに送られてきたりと(申請に1週間かかる)、日本ではあり得ない対応だった！(かなりルーズである！)航空券も自分で取る必要がある。

私は代理会社にビザと航空券の取得はお願いした。(お金かかっても断然楽！)

 

申し込みで苦労したが、初海外だったし、ロシア語はまあ話せなくとも、英語が恐らく通じるだろう。

何とか1ヶ月頑張るぞ！

と、希望に燃えつつ興奮もしてた。そして、いよいよロシアに行くことになる...。

 

3.空港にて

モスクワのシェレメーチエヴォ国際空港に着いた。とりあえず、飛行機の時間も遅れなかったし、ロシアに無事着いてとりあえず安心はした。しかし、、、

 

びっくり(⊙︎ﾛ⊙︎)、空港で英語が通じない！？

 

成田→モスクワの便から、モスクワ→アストラハンの便への乗り換えの間、5時間ぐらい時間が余ってた。

暇だったから、空港の売店に行った。店員に欲しい物を英語で説明したが、まさかの、

 

Я не говорю по-английски(わたし英語話せませーん)！

 

これにはびっくりした。

とんでもないところに来てしまった...。

空港の職員なんだからせめて英語話せとけよ...。

と思ったが、

まあ人生で初めてロシア人とロシア語で話す機会だし！

と思って張り切って話した。

ひたすら、Это、Это(これ、これ)と言いまくったがまあ通じてよかった！？

 

こんな感じで私はアストラハンに向かう。

残り1ヶ月大丈夫か！？

 

次回に、続く...