Damerau–Levenshtein距離
formとfromは隣り合う2文字を入れ替えるだけなので距離は1、kittenとsittingは3です。0から1の類似度も表示するので、打ち間違いやほぼ同じ名前の検出に役立ちます。ブラウザで無料で使えます。
- 無料
- ブラウザで動作
- 登録不要
- データは端末の外に出ません
無料で実行
計算例
- テキスト a
- kitten
- テキスト b
- sitting
- 距離
- 3
- Len a
- 6
- Len b
- 7
- 最大長
- 7
Damerau–Levenshtein距離は、挿入・削除・置換・隣接する2文字の転置という一文字単位の操作で、ある文字列を別の文字列へ変えるのに何回必要かを数える古典的な編集距離です。最後の転置こそが通常のLevenshtein距離との違いであり、実世界の誤入力に特に有効です。利用者は隣り合うキーを入れ替えることが多く（formとfrom、tehとthe）、それは1ステップであるべきで、2回の置換ではありません。本機能はOptimal String Alignment形式を純粋な動的計画法の表で実装するため、どの実行環境でも同じ整数になります。2つのテキストと任意の大文字小文字区別フラグを送ると、距離・両長さ・0から1の正規化類似度・identicalフラグが返ります。
Damerau–Levenshteinが測るものと通常のLevenshteinとの違い
編集距離は、元の文字列を目標の文字列に書き換えるのに必要な単位変更の回数を問います。古典的Levenshteinは3つの単位操作を許します。1文字の挿入、1文字の削除、1文字の置換です。
それぞれコストは1です。Damerauの拡張は4つ目の操作を加えます。隣接する2文字を1単位コストで入れ替える転置です。
この拡張はキーボードでの実際の誤入力と一致します。例えば ab と ba は Damerau–Levenshtein では隣接転置1回、通常のLevenshteinでは置換2回です。kitten と sitting は依然として3（教科書のLevenshtein例と同じ）で、最短経路は転置1回ではなく置換と挿入を使います。
動的計画行列のセル (i, j) は削除・挿入・置換または一致の最小値であり、各接頭辞の末尾2文字が交差対ならセル (i−2, j−2) からの転置も候補にします。OSA は誤入力補正で多くのライブラリが Damerau–Levenshtein と呼ぶ形です。同一部分文字列への重複する転置を禁じ、時間・空間とも O(n·m) の単純な計量に保ちます。
空文字列は有効です。 空から任意文字列への距離はその長さ、2つの空の距離は0です。同一文字列は常に距離0・類似度1となり、任意の大文字小文字正規化後も同様です。
入力する内容と結果の見方
どちらも空で構いません。false にすると表を埋める前に両方を小文字化します。各文字列は5000文字までで、二次の表が無料エッジ経路で有界に保たれます。
短い formula 文字列が OSA 再帰を答えの横に示します。検証失敗は課金されません。対話用途では入力を短くし、テストで整数距離と丸め類似度を固定すれば、言語モデルや外部辞書なしで再現可能なファジー得点が得られます。
この距離が役立つ場面
商品検索や在庫ツールは転置付き編集距離で SKU やブランドの近い候補を順位付けし、その後で遅い意味モデルに委ねます。CRM と重複排除パイプラインは距離が最大1または2で類似度が固定閾値を超える行を候補として印を付け、単純等価や通常のLevenshteinでは過小評価されがちな文字入れ替えを捉えます。
スペルチェックのデモや教室演習は、form と from を距離1と判定し、トークン課金ではなく透明な固定料金を取る決定的オラクルを必要とします。無効入力は残高を消費しません。
整数距離を独自の閾値方針と組み合わせ—厳密キーは距離0のみ、積極的誤入力修正は距離1、ソフト結合ヒントは類似度 0.8 超—すれば、検索エンジン全体や独自 NLP スタックを建てずに監査可能なファジー照合の部品が得られます。
活用例
誤入力に強い商品・SKU照合
購入者や仕入先の文字列が真の SKU から1回の入れ替えまたは1編集離れているとき、埋め込みモデルを呼ばずにカタログ候補を順位付けします。
CRM とレコードの重複排除
隣接文字の入れ替えがよく起きる氏名や住所のほぼ重複に、固定の距離または類似度閾値で印を付けます。
宿題とアルゴリズムのデモ
kitten/sitting と ab/ba で OSA 動的計画を示し、転置コストが通常の Levenshtein の横で見えるようにします。
よくある質問
Damerau–Levenshtein距離とは何ですか？
ある文字列を別の文字列に変えるのに必要な、挿入・削除・置換・隣接文字転置の最小回数です。
通常のLevenshtein距離とどう違いますか？
通常のLevenshteinには転置がなく、隣同士の入れ替えは置換2回になります。Damerau–Levenshtein (OSA) は隣接交換を1編集と数え、実キーボードの誤入力により適合します。
空文字列は許可されますか？
はい。 空から非空への距離はその長さ、2つの空は距離0・類似度1です。
類似度は何を表しますか？
1から、距離を長いほうの文字数で割った値を引いたものです。kittenとsittingは距離3で長いほうが7文字なので、類似度は約0.571428571429です。同じ文字列なら1になります。
大文字と小文字は区別されますか？
初期設定では区別し、Kittenとkittenの距離は1です。区別をオフにすると、両方を小文字にしてから計算するため、大文字と小文字の違いは距離に加わりません。
関連ツール
開発者向け — APIアクセス
このページの機能はすべてAPIからも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。
エンドポイント
Bearerトークンで認証し、POST1回でタスクをキューに登録します。結果はWebhookまたは署名付きリンクで受け取れます。
お使いのスタックから呼び出す
curl -X POST https://api.kit.forhosting.com/str/damerau-levenshtein \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"text_a":"kitten","text_b":"sitting"}'const res = await fetch("https://api.kit.forhosting.com/str/damerau-levenshtein", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"text_a": "kitten",
"text_b": "sitting"
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/str/damerau-levenshtein",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"text_a": "kitten",
"text_b": "sitting"
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/str/damerau-levenshtein", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"text_a":"kitten","text_b":"sitting"}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"text_a":"kitten","text_b":"sitting"}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/str/damerau-levenshtein", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)リクエスト例
{
"text_a": "kitten",
"text_b": "sitting"
}レスポンス例
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "str.damerau_levenshtein",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}非同期APIです。task_idは即時に返ります。ポーリングは1秒あたり1リクエストまでです。
料金
単価はすべて公開しています。トークン換算や独自クレジットはありません。失敗したタスクは課金されません。
エラー
| HTTP | コード | 意味 |
|---|---|---|
401 | unauthorized | APIキーが無効か、指定されていません。Authorizationヘッダーを確認してください。 |
402 | insufficient_balance | 残高が不足しています。チャージ後に再度お試しください。 |
404 | unknown_type | 指定されたタスクタイプは存在しません。タイプ名を確認してください。 |
429 | rate_limited | リクエストが多すぎます。しばらく待ってから再度お試しください。 |
技術的な注記
無料のブラウザ経路と前払いAPIは同一モジュールを共有するため、課題チェックやファジー閾値、本番パイプラインが「十分近いか」で食い違うことはありません。
Damerau–Levenshteinが測るものと通常のLevenshteinとの違い
本エンドポイントは Optimal String Alignment (OSA) 再帰を用います。
入力契約・応答フィールド・検証ルール
必須の文字列フィールド text_a（別名 a, string1, s1, left, first, source）と text_b（別名 b, string2, s2, right, second, target）を含む JSON 本文を POST してください。欠落や非文字列は invalid_input でフィールド名を示して失敗します。任意の case_sensitive は既定 true で Kitten と kitten が異なり得ます。成功時は text_a, text_b, case_sensitive を返し、distance を非負整数で、正規化後の len_a, len_b, max_len を、similarity を (max_len − distance) / max_len の12桁丸め（両長0なら1）で報告し、distance が0のときだけ identical を true にします。例: text_a kitten と text_b sitting は distance 3、長さ6と7、max_len 7、similarity 約 0.571、identical false。例: text_a ab と text_b ba は隣接交換により distance 1。
Damerau–Levenshtein API が価値を発揮する場面
実装は純粋 parse の tier A のため、成功した各呼び出しは公開の基準価格 $0.002 で、モデルトークンも外向きネットワークもありません。
技術的な質問
比較は大文字小文字を区別しますか？
既定でははい（case_sensitive true）。case_sensitive を false にすると計算前に両方を小文字化し、Kitten と kitten が一致します。
Damerau–Levenshtein計算機の料金は？
ブラウザツールは無料です。API は前払い KIT 残高で成功1回あたり $0.002、無効入力は課金されません。