背景：面接後のトランスクリプトを振り返るという課題は、AI面接トランスクリプトレビューをきっかけに整理しました。本稿では製品の話ではなく、2つの文字列の修正量を測る実装だけを扱います。

TypeScriptで編集距離を実装する：面接トランスクリプトの回答差分をO(min(m,n))メモリで測る

面接で実際に話した回答と、振り返り後に書き直した回答は、同じ主旨でも少しずつ違います。「どれだけ直したか」を数えるだけなら、編集距離（Levenshtein distance）が使えます。

この記事で実装する関数は、挿入・削除・置換をそれぞれ1回として最小回数を返します。動的計画法の表全体は保持せず、短い方の文字列に対応する2行だけを持つため、メモリ量は O(min(m, n)) です。

• 距離が 0: 文字列は同一です。
• 距離が小さい: 表現の微修正である可能性があります。
• 距離が大きい: 構成や具体例が大きく変わっています。

編集距離は回答の「良し悪し」を採点する値ではありません。変更量を機械的に見つけ、見直す場所を絞るための値です。

問題を操作に分解する

たとえば 結果を共有しました を 結果をすぐ共有しました に変えるとき、必要なのは すぐ の挿入です。編集距離では次の3操作を数えます。

操作	例
挿入	結果を共有しました → 結果を**すぐ**共有しました
削除	私は**主に**設計しました → 私は設計しました
置換	結果 → 成果

文字列 left の先頭 i 文字と right の先頭 j 文字の距離を dp[i][j] とすると、最後の文字が同じかどうかで次のように決まります。

dp[i][j] = min(
  dp[i - 1][j] + 1,                  // left 側の1文字を削除
  dp[i][j - 1] + 1,                  // right 側の1文字を挿入
  dp[i - 1][j - 1] + 置換コスト      // 同じなら0、異なれば1
)

ここで重要なのは、dp[i][j] が参照するのは「上」「左」「左上」だけだという点です。前の行と現在の行があれば、表全体を残す必要はありません。

TypeScript実装

Array.from を使うと、UTF-16のコードユニットではなくコードポイント単位で走査できます。短い方を列に固定しているので、入力順が逆でも必要なバッファ量は増えません。

export function levenshtein(left: string, right: string): number {
  let row = Array.from(left);
  let column = Array.from(right);

  // バッファは常に短い方に合わせる。
  if (row.length < column.length) [row, column] = [column, row];

  let previous = new Uint32Array(column.length + 1);
  let current = new Uint32Array(column.length + 1);

  // 空文字列から column の先頭 j 文字へは、j 回の挿入が必要。
  for (let j = 0; j <= column.length; j++) previous[j] = j;

  for (let i = 1; i <= row.length; i++) {
    // row の先頭 i 文字から空文字列へは、i 回の削除が必要。
    current[0] = i;

    for (let j = 1; j <= column.length; j++) {
      const replace =
        previous[j - 1] + Number(row[i - 1] !== column[j - 1]);
      const remove = previous[j] + 1;
      const insert = current[j - 1] + 1;

      current[j] = Math.min(replace, remove, insert);
    }

    [previous, current] = [current, previous];
  }

  return previous[column.length];
}

実行時間は O(m × n) です。一般的な面接回答のような数百文字程度なら十分に軽く、保存する数値は短い方の長さに比例します。

差分を長さで正規化する

100文字の回答で距離10と、10文字の回答で距離10は同じ重さではありません。比較画面などでは、距離を最大長で割った差分率も一緒に出すと扱いやすくなります。

export function similarity(left: string, right: string): number {
  const length = Math.max(Array.from(left).length, Array.from(right).length);
  return length === 0 ? 1 : 1 - levenshtein(left, right) / length;
}

この値は0から1の範囲です。たとえば 結果 と 成果 の編集距離は1、類似度は 1 - 1 / 2 = 0.5 です。閾値を決める場合は、実際のデータを見てから決めます。一般的な「0.8以上なら同じ」といった値をそのまま採用すると、短文で誤判定しやすくなります。

動作確認

次のケースをBunで実行しました。空文字列、同一文字列、挿入、置換、日本語、入力順を反転した場合を含めています。

import { strict as assert } from "node:assert";

assert.equal(levenshtein("", ""), 0);
assert.equal(levenshtein("STAR", "STAR"), 0);
assert.equal(levenshtein("STAR", "SSTAR"), 1);
assert.equal(levenshtein("結果", "成果"), 1);
assert.equal(levenshtein("私は設計しました", "私は設計をしました"), 1);
assert.equal(levenshtein("kitten", "sitting"), 3);
assert.equal(levenshtein("sitting", "kitten"), 3);
assert.equal(similarity("", ""), 1);
assert.equal(similarity("結果", "成果"), 0.5);

console.log("9 assertions passed");

出力は次のとおりでした。

9 assertions passed

実務での注意点

文字単位と見た目の1文字は一致しないことがある

Array.from はコードポイント単位です。結合文字、絵文字の修飾子、複数コードポイントからなる書記素クラスタを「見た目の1文字」として扱いたい場合は、分割処理を Intl.Segmenter に差し替えます。編集距離のDP部分はそのまま再利用できます。

const segmenter = new Intl.Segmenter("ja", { granularity: "grapheme" });

function graphemes(text: string): string[] {
  return [...segmenter.segment(text)].map(({ segment }) => segment);
}

距離だけでは、何を直したか分からない

2行だけのDPは距離を省メモリで求めるための実装です。実際の挿入・削除・置換箇所までUIに表示するには、全表を保持して逆向きにたどる方法、または Myers diff のような別アルゴリズムを選びます。まず変更量だけで十分か、差分表示まで必要かを分けて設計するのが安全です。

まとめ

• 編集距離は、2つの回答テキストの最小修正回数を測れます。
• 参照するセルは3つだけなので、DPの2行で O(min(m, n)) メモリにできます。
• 距離は品質スコアではなく、見直し対象を見つけるための指標です。
• 表示単位や差分の復元が必要なら、入力の分割方法とアルゴリズムを追加で選びます。

技術面接では、DPの漸化式だけで終わらず、「なぜ2行で足りるか」「差分箇所を復元するには何が変わるか」まで説明できると、設計上のトレードオフを具体的に伝えられます。