# 機能設計書 75-編集距離

## 概要

本ドキュメントは、F#コンパイラにおける編集距離計算機能の設計を記述する。編集距離は、2つの文字列間の類似度を測定するメトリクスであり、コンパイラの候補サジェスト機能（スペルミス修正提案）の基盤として使用される。

### 本機能の処理概要

**業務上の目的・背景**：プログラミングにおいて、開発者が識別子名（変数名、関数名、型名など）をタイプミスすることは珍しくない。コンパイラが単に「識別子が見つかりません」というエラーを出力するだけでなく、「もしかして○○ではありませんか？」という形で類似した識別子を提案することで、開発者の生産性を向上させることができる。本機能は、ユーザーが入力した文字列と既存の識別子間の類似度を計算し、最も近い候補を特定するための基盤を提供する。

**機能の利用シーン**：コンパイル時にF#コンパイラが未解決の識別子を検出した際、スコープ内の既存識別子と比較して最も近い候補を提案するために使用される。また、IDEの補完機能やリファクタリング機能でも活用可能。

**主要な処理内容**：
1. Jaro類似度の計算（共通文字と転置の評価）
2. Jaro-Winkler距離の計算（先頭一致のボーナス付加）
3. Damerau-Levenshtein距離の計算（挿入・削除・置換・転置の編集操作数）
4. 類似度スコアに基づく候補のランキング

**関連システム・外部連携**：コンパイラの名前解決モジュール、エラー報告システム、診断メッセージ生成システムと連携する。

**権限による制御**：本機能は純粋な計算機能であり、権限制御は存在しない。

## 関連画面

本機能はコンパイラ内部機能であり、直接関連する画面は存在しない。

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | - | - | - |

## 機能種別

文字列計算 / アルゴリズム / ユーティリティ

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| s1 / a | string | Yes | 比較対象文字列1 | null不可 |
| s2 / b | string | Yes | 比較対象文字列2 | null不可 |

### 入力データソース

- 未解決の識別子名（ユーザー入力）
- スコープ内の既存識別子リスト

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| JaroWinklerDistance結果 | float | 0.0〜1.0の類似度スコア（1.0が完全一致） |
| CalculateEditDistance結果 | int | 編集操作の最小回数（0が完全一致） |

### 出力先

- 呼び出し元への返却値

## 処理フロー

### 処理シーケンス

```
【Jaro-Winkler距離】
1. マッチング半径の計算
   └─ minLen / 2 + minLen % 2
2. 共通文字の検出
   └─ existsInWinで各文字が相手文字列の対応位置付近に存在するか判定
3. 転置数の計算
   └─ 共通文字の順序の違いを計数
4. Jaroスコアの計算
   └─ (m1/|s1| + m2/|s2| + (mc-t)/mc) / 3
5. 先頭一致長の計算
   └─ 最大4文字まで
6. Winklerボーナスの付加
   └─ jaroScore + (l * 0.1 * (1 - jaroScore))

【Damerau-Levenshtein距離】
1. 動的計画法テーブルの初期化
   └─ lastLine, lastLastLine, actLineを準備
2. 各位置での最小コスト計算
   └─ 削除、挿入、置換の最小値
3. 転置のチェック
   └─ 隣接文字の交換でコストを削減できるか判定
4. 最終行の末尾値を返却
```

### フローチャート

```mermaid
flowchart TD
    A[開始: JaroWinklerDistance] --> B[jaro関数呼び出し]
    B --> C[マッチング半径計算]
    C --> D[共通文字検出ループ]
    D --> E[転置数計算]
    E --> F[Jaroスコア計算]
    F --> G[先頭一致長計算]
    G --> H{一致長 > 4?}
    H -->|Yes| I[l = 4.0]
    H -->|No| J[l = 一致長]
    I --> K[Winklerボーナス付加]
    J --> K
    K --> L[結果返却]

    M[開始: CalculateEditDistance] --> N{|a| > |b|?}
    N -->|Yes| O[calcDamerauLevenshtein(a, b)]
    N -->|No| P[calcDamerauLevenshtein(b, a)]
    O --> Q[DPテーブル初期化]
    P --> Q
    Q --> R[i=1からa.Lengthまでループ]
    R --> S[j=1からb.Lengthまでループ]
    S --> T[削除/挿入/置換の最小コスト]
    T --> U{転置可能?}
    U -->|Yes| V[転置コストも考慮]
    U -->|No| W[次のj]
    V --> W
    W --> X{jループ終了?}
    X -->|No| S
    X -->|Yes| Y[行をスワップ]
    Y --> Z{iループ終了?}
    Z -->|No| R
    Z -->|Yes| AA[lastLine末尾を返却]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-75-01 | Jaro-Winkler範囲 | 結果は0.0〜1.0の範囲（1.0が最も類似） | 常時 |
| BR-75-02 | 編集距離範囲 | 結果は0以上の整数（0が完全一致） | 常時 |
| BR-75-03 | 先頭一致ボーナス | Jaro-Winklerでは先頭4文字までの一致にボーナス | 常時 |
| BR-75-04 | 長い文字列優先 | Damerau-Levenshteinでは長い方を第一引数に | 常時 |
| BR-75-05 | NaN処理 | Jaroスコアがである場合は0.0を返却 | 空文字列等 |

### 計算ロジック

- **Jaroスコア計算式**:
  ```
  jaro = (m1/|s1| + m2/|s2| + (mc-t)/mc) / 3
  ```
  - m1, m2: 各文字列での共通文字数
  - mc: max(m1, m2)
  - t: 転置数

- **Jaro-Winkler計算式**:
  ```
  JW = jaro + (l * p * (1 - jaro))
  ```
  - l: 先頭一致文字数（最大4）
  - p: スケーリング係数（0.1）

- **マッチング半径計算式**:
  ```
  matchRadius = minLen / 2 + minLen % 2
  ```

## データベース操作仕様

本機能はデータベース操作を行わない。

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| - | NaN結果 | 空文字列や長さ0の場合 | 0.0を返却 |

### リトライ仕様

純粋関数であり、リトライは不要。

## トランザクション仕様

本機能はトランザクション管理を必要としない。

## パフォーマンス要件

- Jaro-Winkler: O(n*m) の時間計算量（n, mは文字列長）
- Damerau-Levenshtein: O(n*m) の時間計算量、O(m) の空間計算量
- 短い文字列（識別子名）に対して高速に動作すること

## セキュリティ考慮事項

- 純粋な文字列比較関数であり、セキュリティリスクは低い
- 入力文字列のサイズに制限はないが、極端に長い文字列はパフォーマンスに影響

## 備考

- Jaro-Winkler距離は名前の類似性評価に特に効果的（人名のマッチングに起源）
- Damerau-Levenshtein距離は一般的なスペルミス検出に適している
- 両アルゴリズムを組み合わせて使用することで、より精度の高いサジェストが可能

---

## コードリーディングガイド

本機能を理解するために参照すべきファイルと、推奨する読み解き順序を以下に示す。

### 推奨読解順序

#### Step 1: ヘルパー関数を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | EditDistance.fs | `src/Compiler/Utilities/EditDistance.fs` | existsInWin関数 |

**主要処理フロー**:
- **9-21行目**: existsInWin関数 - 指定位置の周辺に文字が存在するかチェック
- **10行目**: startAt = Max(0, offset - rad) - 検索開始位置
- **11行目**: endAt = Min(offset + rad, str.Length - 1) - 検索終了位置
- **16-21行目**: 再帰的な文字検索

**読解のコツ**: `inline`キーワードにより、この関数は呼び出し箇所でインライン展開され、パフォーマンスが向上する。

#### Step 2: Jaro距離を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | EditDistance.fs | `src/Compiler/Utilities/EditDistance.fs` | jaro関数 |

**主要処理フロー**:
- **23-28行目**: マッチング半径の計算
- **29-38行目**: nextChar関数 - 次の共通文字を検索
- **42-71行目**: 共通文字の検出と転置数計算
- **76-80行目**: Jaroスコア計算式の適用
- **83行目**: NaN処理

**読解のコツ**: `struct`キーワードは値タプルを生成し、ヒープ割り当てを回避する最適化。

#### Step 3: Jaro-Winkler距離を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | EditDistance.fs | `src/Compiler/Utilities/EditDistance.fs` | JaroWinklerDistance関数 |

**主要処理フロー**:
- **87-88行目**: jaro関数の呼び出し
- **92-96行目**: 先頭一致長の再帰的計算（calcL）
- **98行目**: 最大4文字に制限
- **100-101行目**: Winklerボーナスの計算

#### Step 4: Damerau-Levenshtein距離を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | EditDistance.fs | `src/Compiler/Utilities/EditDistance.fs` | calcDamerauLevenshtein関数 |

**主要処理フロー**:
- **107-111行目**: DPテーブルの初期化
- **113-114行目**: 外側ループ（文字列aの各位置）
- **116-127行目**: 内側ループ（削除・挿入・置換・転置の最小コスト）
- **129-132行目**: 行のスワップ（メモリ効率化）
- **134行目**: 最終結果の返却

**読解のコツ**: 動的計画法の典型的なパターン。3行分のみを保持することで、O(m)の空間計算量を実現。

### プログラム呼び出し階層図

```
呼び出し元（名前解決モジュール等）
    │
    ├─ JaroWinklerDistance
    │      │
    │      └─ jaro
    │             │
    │             ├─ nextChar（再帰）
    │             │      └─ existsInWin
    │             │
    │             └─ loop（再帰・複数）
    │                    └─ existsInWin
    │
    └─ CalculateEditDistance
           │
           └─ calcDamerauLevenshtein
                  └─ 動的計画法ループ
```

### データフロー図

```
[入力]                    [処理]                              [出力]

s1, s2 ─────────────────▶ jaro ────────────────────────────▶ jaroScore (float)
    │                        │
    │                        ├─ matchRadius計算
    │                        │
    │                        ├─ 共通文字検出
    │                        │      └─ existsInWin
    │                        │
    │                        └─ 転置数計算
    │
    └───────────────────▶ JaroWinklerDistance
                             │
                             ├─ 先頭一致長計算
                             │
                             └─ Winklerボーナス ────────────▶ JW距離 (float)

a, b ───────────────────▶ CalculateEditDistance
                             │
                             └─ calcDamerauLevenshtein
                                    │
                                    ├─ DPテーブル更新
                                    │
                                    └─ 最小編集距離 ─────────▶ 編集距離 (int)
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| EditDistance.fs | `src/Compiler/Utilities/EditDistance.fs` | ソース | 編集距離計算の主実装 |
| EditDistance.fsi | `src/Compiler/Utilities/EditDistance.fsi` | シグネチャ | 公開APIの定義 |
