ブラウザでJavaScriptでレーベンシュタイン距離を計算する(JavaScriptと)HTMLのコード
「レーベンシュタイン距離」は全ての種類の文字に対して利用できます。
「正規化されたレーベンシュタイン距離」が小さいほど、2つの文字は似ています。
ちなみに、「レーベンシュタイン距離」は文字数に比例して大きくなるので、「レーベンシュタイン距離」を2つの文字の文字数のうち大きい方で割った「正規化されたレーベンシュタイン距離」を利用します。
「正規化されたレーベンシュタイン距離」は0以上1以下の実数に収まります。
Githubで(JavaScriptと)HTMLのソース コードをパブリック ドメインで公開しております。
マイクロソフトのBing検索エンジンで「github eliphas1810-tools」などで検索してみてください。
残念ながらグーグル検索エンジンでは検索できません。
不具合が有るかもしれないので利用は自己責任でお願いいたします。
2024年7月31日時点の最新のChromeとFirefoxで動作を確認しました。
コピーする場合は、2文字の全角空白を4文字の半角空白に置換してください。
<!DOCTYPE html>
<html lang="ja">
<head>
<meta charset="UTF-8" />
<title>レーベンシュタイン距離の計算</title>
</head>
<body>
<div>
<input type="text" id="firstString" size="80"></input>
</div>
<br />
<div>
<input type="text" id="secondString" size="80"></input>
</div>
<br />
<div>
<button type="button" id="calculateLevenshteinDistance">レーベンシュタイン距離を計算</button>
</div>
<br />
<p id="message"></p>
<br />
<p> レーベンシュタイン距離: <span id="levenshteinDistance"></span>
</p>
<br />
<p> 2つの文字の文字数のうち最大文字数で割って0以上1以下に正規化されたレーベンシュタイン距離: <span id="normalizedLevenshteinDistance"></span>
</p>
<br />
<p> ※レーベンシュタイン距離と、正規化されたレーベンシュタイン距離は、小さいほど、2つの文字は似ています。</p>
<script>
function $(id) {
return document.getElementById(id);
}
//レーベンシュタイン距離を計算
function calculateLevenshteinDistance(firstString, secondString) {
var maxX = firstString.length;
var maxY = secondString.length;
var table = [];
for (var x = 0; x <= maxX; x++) {
table[x] = [];
table[x][0] = x;
}
for (var y = 0; y <= maxY; y++) {
table[0][y] = y;
}
for (var x = 1; x <= maxX; x++) {
for(var y = 1; y <= maxY; y++) {
var cost = null;
if (firstString.charAt(x - 1) == secondString.charAt(y - 1)) {
cost = 0;
} else {
cost = 1;
}
table[x][y] = Math.min(
table[x - 1][y] + 1,
table[x][y - 1] + 1,
table[x - 1][y - 1] + cost
);
}
}
return table[maxX][maxY];
}
//2つの文字の文字数のうち最大文字数で割って、0以上1以下に正規化されたレーベンシュタイン距離を計算
function normalizeLevenshteinDistance(firstString, secondString) {
//レーベンシュタイン距離を計算
var levenshteinDistance = calculateLevenshteinDistance(firstString, secondString);
return (levenshteinDistance / Math.max(firstString.length, secondString.length));
}
$("calculateLevenshteinDistance").onclick = function () {
$("message").innerHTML = "";
$("levenshteinDistance").innerHTML = "";
$("normalizedLevenshteinDistance").innerHTML = "";
var firstString = $("firstString").value;
var secondString = $("secondString").value;
if (firstString.length <= 0 || secondString.length <= 0) {
$("message").innerHTML = " 1文字以上の2つの文字を入力してください。";
return;
}
$("levenshteinDistance").innerHTML = calculateLevenshteinDistance(firstString, secondString);
$("normalizedLevenshteinDistance").innerHTML = normalizeLevenshteinDistance(firstString, secondString);
};
</script>
</body>
</html>
