跳到主要内容

東京大学 情報理工学系研究科 創造情報学専攻 2005年8月実施 筆記試験 第1問

Author​

itsuitsuki

Description​

ある二つの文字列 の編集距離はつぎの 3 つの操作を行うことにより を に変換するのに要する操作の最低回数である．

  • 1 文字挿入する．
  • 1 文字削除する．
  • 1 文字を他の 1 文字に置き換える． たとえば， は に，文字 ‘p’ を削除することにより に変換できるため，編集距離は 1 である．

(1) ， の編集距離を求めなさい．

(2) を文字列 の頭から 番目までの部分列とし， を と の編集距離を表すものとする． の間に成り立つ再帰式を記述しなさい．

(3) (2) の再帰式に基づき効率良く編集距離を計算するアルゴリズムを示し，そのアルゴリズムの時間，空間計算量について述べなさい．

(4) (3) のアルゴリズムに基づき， と の編集距離を求めなさい．

(5) 編集距離の応用として考えられるものを 3 つ挙げなさい．

Description (English)​

The edit distance between two strings and is defined as the minimum number of the following operations required to transform into .

  • insert one character
  • delete one character
  • substitute one character by another character For example, is trasnformed into by deleting the character ‘p’; therefore the edit distance is 1.

(1) Answer the edit distance between and .

(2) Let’s denote as the prefix of length of a given , as the edit distance between and . Write down the recursive formula that holds between and .

(3) Describe an algorithm for calculating the edit distance between two given strings based on the recursive function described in (2). Show its complexity in both space and time.

(4) Calculate the edit distance between and .

(5) Describe three applications of the edit distance.

目录