ホーム コンピュータ レーベンシュタイン距離の計算 作成日: 2026年7月20日 21:33 レーベンシュタイン距離の計算 入力 1つ目の文字列kitten2つ目の文字列sitting コンピュータ レーベンシュタイン距離の計算 2つの文字列間のレーベンシュタイン距離（編集距離）を計算します。一方の文字列をもう一方に変換するのに必要な、1文字単位の挿入・削除・置換の最小回数と、類似度の割合を求めます。 入力 文字列 1つ目の文字列 変換元となる文字列です。 2つ目の文字列 変換先となる文字列です。 結果 値を入力すると計算結果が表示されます。 計算結果 編集距離 kittenをsittingに変換するのに必要な、1文字単位の挿入・削除・置換の最小回数です。 類似度 % 2つの文字列がどれだけ似ているかを表します。1から、編集距離を長い方の文字列の長さで割った値を引いて求めます。 共有 レポートを印刷 リセット 埋め込み この計算機を埋め込む プレビュー このコードをページに貼り付けると計算機を表示できます。 コードをコピー この計算を共有 このリンクを開くと、入力した値がそのまま表示されます。 リンクをコピー 共有する XFacebookLINE メール 最終更新: 2026-07-01 レーベンシュタイン距離 レーベンシュタイン距離は編集距離とも呼ばれ、一方の文字列をもう一方に変えるのに必要な1文字単位の編集の最小回数を数えることで、2つの文字列がどれだけ異なるかを測ります。許される編集は挿入・削除・置換の3種類で、いずれも1回として数えます。この計算機は2つの文字列を受け取り、その距離と類似度の割合を返します。スペルチェック、あいまい検索、DNAなどの配列比較に役立ちます。 3種類の編集操作 2つの文字列間のあらゆる変換は、3つの基本操作の組み合わせで表せます。挿入は1文字を追加し、削除は1文字を取り除き、置換は1文字を別の文字に置き換えます。レーベンシュタイン距離は、これらの最も少ない手数を求めます。置換は削除と挿入の2手ではなく1手として数えるため、1文字の変更は常に1回の編集です。 この尺度は1965年にウラジーミル・レーベンシュタインが定義したもので、より古いハミング距離の計算を一般化したものです。ハミング距離は置換のみを、しかも同じ長さの文字列に対してのみ許しますが、レーベンシュタイン距離は挿入と削除も許すため、長さの異なる文字列も扱えます。 動的計画法の表 距離は表 DD を埋めて計算します。表は1つ目の文字列の各文字に対応する行（先頭に空の行を加える）と、2つ目の文字列の各文字に対応する列（先頭に空の列を加える）からなります。マス D[i][j]D[i][j] は、文字列Aの先頭ii文字と文字列Bの先頭jj文字の編集距離を表します。 先頭の行と列は空文字列に対する編集回数を数えるので、D[i][0]=iD[i][0] = i、D[0][j]=jD[0][j] = j となります。その他のマスはすべて、次の3つの候補の最小値です。 D[i][j]=min{D[i−1][j]+1(削除)D[i][j−1]+1(挿入)D[i−1][j−1]+c(置換)D[i][j] = \min \begin{cases} D[i-1][j] + 1 & \text{(削除)} \\ D[i][j-1] + 1 & \text{(挿入)} \\ D[i-1][j-1] + c & \text{(置換)} \end{cases}D[i][j]=min⎩⎨⎧D[i−1][j]+1D[i][j−1]+1D[i−1][j−1]+c(削除)(挿入)(置換) ここで置換コスト cc は、文字が一致すれば0、異なれば1です。答えは右下のマスにあります。表を埋めるには2つの長さの積 m×nm \times n に比例する時間がかかります。 計算例 定番の組み合わせ「kitten」と「sitting」を考えます。表の最適な経路をたどると、3回の編集が得られます。 kitten→sitten(k→s に置換)sitten→sittin(e→i に置換)sittin→sitting(g を挿入)\begin{aligned} \text{kitten} &\rightarrow \text{sitten} && \text{(k} \rightarrow \text{s に置換)} \\ \text{sitten} &\rightarrow \text{sittin} && \text{(e} \rightarrow \text{i に置換)} \\ \text{sittin} &\rightarrow \text{sitting} && \text{(g を挿入)} \end{aligned}kittensittensittin→sitten→sittin→sitting(k→s に置換)(e→i に置換)(g を挿入) これより短い手順は存在しないので、距離は3です。長い方の文字列は7文字なので、類似度は 1−3/7≈0.5711 - 3/7 \approx 0.571、すなわち約57%となります。 類似度とその限界 この計算機は、生の距離を次の式で類似度に正規化します。 S=1−dLmax(m,n)S = 1 - \dfrac{d_L}{\max(m, n)} 長い方の文字列の長さで割ることで、まったく異なる文字列の0%から、完全に一致する文字列の100%までの範囲に収まります。両方が空文字列の場合は一致とみなします。これは一般的な正規化の1つで、ツールによっては長さの合計で割ったり比率ベースの指標を用いたりするため、出典の異なる類似度の数値を直接比較することはできません。 どこで使われるか スペルチェッカーは、誤った単語からの編集距離で修正候補を順位付けします。検索やデータベースのシステムはあいまい検索に用い、名前や住所を引くときの打ち間違いを許容します。バイオインフォマティクスでは、編集距離がDNA・RNA・タンパク質を比較する配列アラインメントの基礎となり、挿入や削除は変異に対応します。素のレーベンシュタインのコストモデルはすべての編集を等しく扱いますが、操作ごとに異なるペナルティが必要な場合や、非常に長い配列を効率よく整列させる必要がある場合には、重み付きコストや専用のアラインメントアルゴリズムで拡張します。 よくある質問 (FAQ)レーベンシュタイン距離とは何ですか？レーベンシュタイン距離は編集距離とも呼ばれ、ある文字列を別の文字列に変えるのに必要な、1文字単位の編集（挿入・削除・置換）の最小回数です。1965年に旧ソ連の数学者ウラジーミル・レーベンシュタインによって導入されました。 たとえば「kitten」と「sitting」の距離は3です。k→sの置換、e→iの置換、末尾へのgの挿入の3手で変換でき、これより短い手順は存在しません。 この値は動的計画法の表を用いて計算します。表の各マスは2つの文字列の接頭辞どうしの編集距離を保持し、計算量は2つの文字列の長さの積に比例します。 ハミング距離との違いは何ですか？ハミング距離は置換のみを数え、同じ長さの文字列に対してのみ定義されます。各位置の文字を1つずつ比較するためです。一方、レーベンシュタイン距離は挿入と削除も許すため、長さの異なる文字列にも使え、位置のずれも捉えられます。 同じ長さの2つの文字列では、レーベンシュタイン距離は常にハミング距離以下になります。置換も使える操作の1つですが、挿入や削除を組み合わせてより少ない手数で済む場合があるためです。 類似度の割合はどのように計算されますか？類似度は 1 − 距離 / max(len_a, len_b) を百分率で表したものです。長い方の文字列の長さで割ることで、0%（まったく異なる）から100%（完全に一致）の範囲に正規化されます。両方が空文字列の場合、類似度は100%と定義します。 これは一般的な正規化の1つです。ツールによっては長さの合計で割ったり、比率ベースの指標を用いたりするため、定義が異なる類似度どうしを直接比較することはできません。 次のおすすめ ハミング距離の計算 同じ長さの2つの文字列を比較し、異なる位置の数（ハミング距離）を求めます。2進数ビット列や任意の文字列に対応しています。 ビッグO記法の増加率 入力サイズ n を入力して、代表的な時間計算量クラス（O(log n) から O(n!) まで）が必要とする演算数を比較します。 詳しく解説シャノンエントロピーの計算 文字列のシャノンエントロピーを計算します。各記号が平均して持つ情報量をビット・ナット・ハートレーで表示。データ圧縮・暗号・機械学習の基礎概念です。 詳しく解説 200+ ツール · 10 言語対応 · 完全無料 アルゴリズムの他の計算 Luhn チェックディジットの計算シャノンエントロピーの計算ハミング距離の計算ビッグO記法の増加率レーベンシュタイン距離の計算 コンピュータの他のカテゴリ ネットワーク 1秒あたりパケット数(pps)の計算CIDRとサブネットマスクの変換IPv4 アドレス表現の変換IPv6サブネットの計算IPアドレス範囲の計算IPスーパーネットの計算MTU から MSS の計算TCP スループットの計算サブネットの計算レイテンシバジェットの計算帯域幅遅延積(BDP)の計算セキュリティ・暗号 chmodパーミッションの計算UUID 衝突確率の計算パスワードのエントロピーハッシュ衝突確率の計算データ・エンコード 2の補数変換Base64エンコードのオーバーヘッドCRCチェックサムGit リポジトリのクローンサイズ推定IEEE 754 浮動小数点ビット表現QRコードの収容文字数Unixタイムスタンプ変換（エポック ⇄ 日時）UTF-8バイト数計算ツールオーディオファイルサイズ計算カラーコードの変換スループット (bps) 換算データ転送時間の計算テキスト → 2進数 / 16進数 / ASCII 変換ナイキストサンプリングレート計算ツールブルームフィルタ サイズ計算メガピクセル・印刷サイズ計算メモリアドレスビット計算圧縮率の計算画素密度（PPI・DPI）の計算画像ファイルサイズの計算色深度・ビット/ピクセルの計算動画ビットレートとファイルサイズ配信帯域幅の計算浮動小数点精度の計算信頼性・ストレージ APIレート制限の計算cron式デコーダー・次回実行時刻の計算MTBF・MTTR・稼働率 計算ツールRAID容量の計算クラウドストレージ料金の計算ハミング符号 ECCビット数計算ツール稼働率SLAの計算複合可用性の計算性能・待ち行列 Apdex スコアの計算CPU実行時間 計算ツールIOPS とスループットの変換M/M/1 待ち行列の計算M/M/c 待ち行列計算ツールアーランC 要員数計算アムダールの法則の計算キャッシュヒット率と実効アクセス時間（AMAT）の計算グスタフソンの法則の計算バッテリー駆動時間の計算ツールリトルの法則の計算平均メモリアクセス時間（AMAT）の計算 この計算機は役に立ちましたか？ 役に立った 改善が必要 改善が必要 どのような点が改善されると良いですか？ フィードバックを送信 Powered by OneCalc ↗
最終更新: 2026-07-01 レーベンシュタイン距離 レーベンシュタイン距離は編集距離とも呼ばれ、一方の文字列をもう一方に変えるのに必要な1文字単位の編集の最小回数を数えることで、2つの文字列がどれだけ異なるかを測ります。許される編集は挿入・削除・置換の3種類で、いずれも1回として数えます。この計算機は2つの文字列を受け取り、その距離と類似度の割合を返します。スペルチェック、あいまい検索、DNAなどの配列比較に役立ちます。 3種類の編集操作 2つの文字列間のあらゆる変換は、3つの基本操作の組み合わせで表せます。挿入は1文字を追加し、削除は1文字を取り除き、置換は1文字を別の文字に置き換えます。レーベンシュタイン距離は、これらの最も少ない手数を求めます。置換は削除と挿入の2手ではなく1手として数えるため、1文字の変更は常に1回の編集です。 この尺度は1965年にウラジーミル・レーベンシュタインが定義したもので、より古いハミング距離の計算を一般化したものです。ハミング距離は置換のみを、しかも同じ長さの文字列に対してのみ許しますが、レーベンシュタイン距離は挿入と削除も許すため、長さの異なる文字列も扱えます。 動的計画法の表 距離は表 DD を埋めて計算します。表は1つ目の文字列の各文字に対応する行（先頭に空の行を加える）と、2つ目の文字列の各文字に対応する列（先頭に空の列を加える）からなります。マス D[i][j]D[i][j] は、文字列Aの先頭ii文字と文字列Bの先頭jj文字の編集距離を表します。 先頭の行と列は空文字列に対する編集回数を数えるので、D[i][0]=iD[i][0] = i、D[0][j]=jD[0][j] = j となります。その他のマスはすべて、次の3つの候補の最小値です。 D[i][j]=min{D[i−1][j]+1(削除)D[i][j−1]+1(挿入)D[i−1][j−1]+c(置換)D[i][j] = \min \begin{cases} D[i-1][j] + 1 & \text{(削除)} \\ D[i][j-1] + 1 & \text{(挿入)} \\ D[i-1][j-1] + c & \text{(置換)} \end{cases}D[i][j]=min⎩⎨⎧D[i−1][j]+1D[i][j−1]+1D[i−1][j−1]+c(削除)(挿入)(置換) ここで置換コスト cc は、文字が一致すれば0、異なれば1です。答えは右下のマスにあります。表を埋めるには2つの長さの積 m×nm \times n に比例する時間がかかります。 計算例 定番の組み合わせ「kitten」と「sitting」を考えます。表の最適な経路をたどると、3回の編集が得られます。 kitten→sitten(k→s に置換)sitten→sittin(e→i に置換)sittin→sitting(g を挿入)\begin{aligned} \text{kitten} &\rightarrow \text{sitten} && \text{(k} \rightarrow \text{s に置換)} \\ \text{sitten} &\rightarrow \text{sittin} && \text{(e} \rightarrow \text{i に置換)} \\ \text{sittin} &\rightarrow \text{sitting} && \text{(g を挿入)} \end{aligned}kittensittensittin→sitten→sittin→sitting(k→s に置換)(e→i に置換)(g を挿入) これより短い手順は存在しないので、距離は3です。長い方の文字列は7文字なので、類似度は 1−3/7≈0.5711 - 3/7 \approx 0.571、すなわち約57%となります。 類似度とその限界 この計算機は、生の距離を次の式で類似度に正規化します。 S=1−dLmax(m,n)S = 1 - \dfrac{d_L}{\max(m, n)} 長い方の文字列の長さで割ることで、まったく異なる文字列の0%から、完全に一致する文字列の100%までの範囲に収まります。両方が空文字列の場合は一致とみなします。これは一般的な正規化の1つで、ツールによっては長さの合計で割ったり比率ベースの指標を用いたりするため、出典の異なる類似度の数値を直接比較することはできません。 どこで使われるか スペルチェッカーは、誤った単語からの編集距離で修正候補を順位付けします。検索やデータベースのシステムはあいまい検索に用い、名前や住所を引くときの打ち間違いを許容します。バイオインフォマティクスでは、編集距離がDNA・RNA・タンパク質を比較する配列アラインメントの基礎となり、挿入や削除は変異に対応します。素のレーベンシュタインのコストモデルはすべての編集を等しく扱いますが、操作ごとに異なるペナルティが必要な場合や、非常に長い配列を効率よく整列させる必要がある場合には、重み付きコストや専用のアラインメントアルゴリズムで拡張します。 よくある質問 (FAQ)レーベンシュタイン距離とは何ですか？レーベンシュタイン距離は編集距離とも呼ばれ、ある文字列を別の文字列に変えるのに必要な、1文字単位の編集（挿入・削除・置換）の最小回数です。1965年に旧ソ連の数学者ウラジーミル・レーベンシュタインによって導入されました。 たとえば「kitten」と「sitting」の距離は3です。k→sの置換、e→iの置換、末尾へのgの挿入の3手で変換でき、これより短い手順は存在しません。 この値は動的計画法の表を用いて計算します。表の各マスは2つの文字列の接頭辞どうしの編集距離を保持し、計算量は2つの文字列の長さの積に比例します。 ハミング距離との違いは何ですか？ハミング距離は置換のみを数え、同じ長さの文字列に対してのみ定義されます。各位置の文字を1つずつ比較するためです。一方、レーベンシュタイン距離は挿入と削除も許すため、長さの異なる文字列にも使え、位置のずれも捉えられます。 同じ長さの2つの文字列では、レーベンシュタイン距離は常にハミング距離以下になります。置換も使える操作の1つですが、挿入や削除を組み合わせてより少ない手数で済む場合があるためです。 類似度の割合はどのように計算されますか？類似度は 1 − 距離 / max(len_a, len_b) を百分率で表したものです。長い方の文字列の長さで割ることで、0%（まったく異なる）から100%（完全に一致）の範囲に正規化されます。両方が空文字列の場合、類似度は100%と定義します。 これは一般的な正規化の1つです。ツールによっては長さの合計で割ったり、比率ベースの指標を用いたりするため、定義が異なる類似度どうしを直接比較することはできません。
