Character Vault
Any Concept / Any System
Compendium
Your System Come To Life
Roll20 for Android
Streamlined for your Tablet
Roll20 for iPad
Streamlined for your Tablet

Personal tools

Difference between revisions of "Script:levenshteinDistance"

From Roll20 Wiki

Jump to: navigation, search
(Created page with "{{stub}}")
 
Line 1: Line 1:
{{stub}}
+
{{script overview
 +
|name=levenshteinDistance
 +
|author={{user profile|235259|Brian}}
 +
|version=1.0
 +
|lastmodified=2015-01-08
 +
}}
 +
 
 +
'''levenshteinDistance''' is a string comparison function. The metric was developed by [[wikipedia:Vladimir Levenshtein|Vladimir Levenshtein]] in 1965. The function tracks the difference between two strings based on single-character changes. In other words, the number of insertions, deletions, and substitutions required to change the first string into the second. This metric is useful for deciding what strings are "close" to being the same, such as finding a partial match against a player or character name.
 +
 
 +
The <code>levenshteinDistance</code> function is added to <code>String.prototype</code>, meaning it can be treated as a function of string objects.
 +
 
 +
Original JavaScript implementation from [http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#JavaScript wikibooks.org].
 +
 
 +
=== Syntax ===
 +
{{syntaxbox top|nocat=true}}
 +
str.levenshteinDistance(''otherStr'')
 +
{{syntaxbox end}}
 +
 
 +
==== Parameters ====
 +
;otherStr
 +
:The string to compare against ''str''.
 +
 
 +
==== Return Value ====
 +
<code>levenshteinDistance</code> returns an integer of the total number of insertions, deletions, and substitutions required to change ''str'' into ''otherStr''.
 +
 
 +
=== Example ===
 +
The distance between "kitten" and "sitting" is 3:
 +
# '''k'''itten {{rarr}} '''s'''itten (substitute "s" for "k")
 +
# sitt'''e'''n {{rarr}} sitt'''i'''n (substitute "i" for "e")
 +
# sittin {{rarr}} sittin'''g''' (insert "g")
 +
 
 +
<pre data-language="javascript">
 +
on('chat:message', function(msg) {
 +
    var params = msg.content.splitArgs(),
 +
        command = params.shift().substring(1).toLowerCase(),
 +
        characterName = params[0],
 +
        potentialCharacters, foundCharacter;
 +
 
 +
    if (msg.type === 'api' && command === 'echocharacter') {
 +
        potentialCharacters = filterObjs(function(obj) { return obj.get('type') === 'character' && obj.get('name').indexOf(who) >= 0; });
 +
        foundCharacter = _.sortBy(potentialCharacters, function(chr) {
 +
            return chr.get('name').toLowerCase().levenshteinDistance(who.toLowerCase());
 +
        })[0];
 +
 
 +
        if (foundCharacter) {
 +
            sendChat('System', characterName + ' interpreted as ' + foundCharacter.get('name'));
 +
        } else {
 +
            sendChat('System', 'Could not find character for ' + characterName);
 +
        }
 +
    }
 +
});
 +
</pre>

Revision as of 16:53, 13 January 2015

API ScriptAuthor: Brian
Version: 1.0
Last Modified: 2015-01-08
Code: levenshteinDistance
Dependencies: None
Conflicts: None

levenshteinDistance is a string comparison function. The metric was developed by Vladimir Levenshtein in 1965. The function tracks the difference between two strings based on single-character changes. In other words, the number of insertions, deletions, and substitutions required to change the first string into the second. This metric is useful for deciding what strings are "close" to being the same, such as finding a partial match against a player or character name.

The levenshteinDistance function is added to String.prototype, meaning it can be treated as a function of string objects.

Original JavaScript implementation from wikibooks.org.

Contents

Syntax

str.levenshteinDistance(otherStr)

Parameters

otherStr
The string to compare against str.

Return Value

levenshteinDistance returns an integer of the total number of insertions, deletions, and substitutions required to change str into otherStr.

Example

The distance between "kitten" and "sitting" is 3:

  1. kitten → sitten (substitute "s" for "k")
  2. sitten → sittin (substitute "i" for "e")
  3. sittin → sitting (insert "g")
on('chat:message', function(msg) {
    var params = msg.content.splitArgs(),
        command = params.shift().substring(1).toLowerCase(),
        characterName = params[0],
        potentialCharacters, foundCharacter;

    if (msg.type === 'api' && command === 'echocharacter') {
        potentialCharacters = filterObjs(function(obj) { return obj.get('type') === 'character' && obj.get('name').indexOf(who) >= 0; });
        foundCharacter = _.sortBy(potentialCharacters, function(chr) {
            return chr.get('name').toLowerCase().levenshteinDistance(who.toLowerCase());
        })[0];

        if (foundCharacter) {
            sendChat('System', characterName + ' interpreted as ' + foundCharacter.get('name'));
        } else {
            sendChat('System', 'Could not find character for ' + characterName);
        }
    }
});