文字列類似度ツールはテキスト文字列 2 つ, String A と String B, を受け取り, デフォルトは kitten と sitting, ブラウザ内で両者の Levenshtein 編集距離を計算します. 1 キー打ち込むたびに結果はライブで再計算され, 3 つの統計カードが距離, 類似度パーセント, 操作数, デフォルトでは 3, 57.1%, 7 を印字し, その下にはプログレスバーと, 先頭の文字から末尾まで各ステップを番号付き, タイプ別カラーで印字する編集ステップ一覧があります. 全てブラウザ内での 2 つの文字列に対する動的計画法のパスで, 何も送信されず, アップロードは一切起きません.
受け取るものと出すもの
入力は横並びの 1 行テキスト欄 2 つで, ラベルは String A と String B, 等幅フォント, それ以外は何も求めません. デフォルトは A に kitten, B に sitting で, 2 つの欄のプレースホルダも同じ 2 つの単語です. 出力は 1 列 3 つのカード: 距離は普通の整数, 類似度は小数 1 桁のパーセント, 操作数は普通の整数. カードの下, プログレスバーが同じパーセントまで満たされ, スクロール可能な一覧が編集ステップ全体を印字し, 各行は 1 から番号付き, タイプ別で着色: 置換は黄色, 挿入は青, 削除は赤, 一致はミュートカラー. ボタンはありません. 打ちながら再計算されます. 計算全体は 2 つの欄の値のメモリ付き読み取りだからです.
距離はどうか計算されるか
距離は古典的な Levenshtein 距離で, (A の長さ + 1) × (B の長さ + 1) セルの動的計画法テーブルで組みます. 各セルは 3 つの隣接セルにコストを足したものの最小を取ります. 上セル + 1 が削除, 左セル + 1 が挿入, 対角セル + コストが一致か置換で, 2 つの文字が等しければコスト 0, 異なれば 1. 比較は文字単位で大文字小文字を区別するので, K と k は異なる文字です. デフォルトの kitten と sitting では, テーブルは 7 × 8 の 56 セルで, 右下のセルは 3 を読みます. k を s に置換, e を i に置換, g を挿入. book と back は 2 で, o の 2 つの位置. flaw と lawn は 2 で, f の削除と末尾の n の挿入.
操作一覧が示すもの
一覧は完成したテーブルのバックトレースで, 右下の角から左上へ戻る歩行です. 各ステップで, トレースは現在の 2 つの文字が等しければ一致を優先し, 次に置換, 次に挿入, 次に削除を選び, 集めたステップを反転して, 先頭から末尾へ印字します. これで得るのは有効な最小編集スクリプトの 1 つで, 唯一ではありません. 同コストの分岐での異なる選択が, 同長の別の一覧を与えます. 一致も一覧に含まれるので, 操作数はスクリプトの長さで, 距離ではありません. kitten と sitting は距離 3 に対し 7 個の操作を印字し, 一致 4 つは i, t, t, n です. kitten と自身は距離 0 で 6 個の操作, 全て一致. flaw と lawn は 5 で, 編集 2 つと一致 3 つ.
類似度パーセントはどうか読まれるか
パーセントは, 長い方の長さから距離を引いたものを長い方の長さで割り, 100 倍, 小数 1 桁で印字されます. デフォルトでは 7 から 3 を 7 で割る 57.1% で, 黄色帯に位置します. 数値とバーは 70 以上で緑, 40 以上で黄, 40 未満で赤になります. 同一の文字列は距離 0 で 100.0%. 大文字小文字の 1 文字の反転, Kitten と kitten は長さ 6 上の距離 1 で 83.3% を印字します. アクセントは 1 文字の差として数えられ, café と cafe は距離 1 で 75.0%. サロゲートペアは 2 ユニットとして数えられるので, a😀b と ab のスマイリーは距離 2 で 50.0%.
結果が空になるとき
どちらかの欄が両端をトリムした後に空だと, 結果は null で, 2 つの入力の下の何もレンダリングされません. カードもバーも一覧もない. 比較は内部や端の空白を除去せず, 空白は空チェックだけに使われるので, 末尾の 1 スペースは編集 1 つです. key の末尾 1 スペース版と key は距離 1 で, 長さ 4 上の 75.0%. 空文字列に対しては, 距離はもう一方の全長なので, abc と空は 3 と 0.0% を計算します. ただし欄が空の間, ページはそれを表示しません.
文字列はどれくらい長くできるか
コードには長さ上限がありません. コストはテーブルサイズ, (A の長さ + 1) × (B の長さ + 1) セルなので, 処理量は 2 つの長さの積に比例して増えます. kitten と sitting は 56 セル, 1,000 文字の 2 つの文字列は約 100 万セル, 10,000 文字の 2 つは約 1 億セルで, ページは計算しますが遅くなります. 入力は 1 行欄なので, とても長い文字列は 1 行に打ち込まれたり貼り付けられたりします.
何ではないか
ツールは比較するだけで, テキストを変換しません. 比較前に余分な空白と行を除去するのは 空白クリーナーの仕事です. 文字列を末尾から先頭へ反転するのは テキスト逆順の仕事です. 文字数を 2 番目の文字列なしに数えるのは 文字カウントの仕事です. 逆順ツールの解説は テキスト逆順ガイドを見てください.