Initial commit

1 files changed, 364 insertions, 0 deletions

diff --git a/src/nimlevenshtein.nim b/src/nimlevenshtein.nim
new file mode 100644
index 0000000..37f715e
--- /dev/null
+++ b/src/nimlevenshtein.nim
@@ -0,0 +1,364 @@
+## A module for fast computation of
+##
+## - Levenshtein (edit) distance and edit sequence manipulation
+## - string similarity
+## - approximate median strings, and generally string averaging
+## - string sequence and set similarity
+##
+## This module uses the standalone version C API of the python-Levenshtein library. So no Python
+## required.
+##
+## The API reflects the API of the python-Levenshtein library. If you want to have a lower level
+## interface, you can import ``nimlevenshtein/wrapper``, which gives you nimified wrapper functions
+## over the C API functions. And if you want to go more lower level, you can use
+## ``nimlevenshtein/binding``.
+
+import nimlevenshtein/wrapper
+
+export EditOp
+export OpCode
+export EditType
+export MatchingBlock
+
+proc distance*(a, b: string): int =
+    ## Compute absolute Levenshtein distance of two strings.
+    runnableExamples:
+        assert distance("Levenshtein", "Lenvinsten") == 4
+        assert distance("Levenshtein", "Levensthein") == 2
+        assert distance("Levenshtein", "Levenshten") == 1
+        assert distance("Levenshtein", "Levenshtein") == 0
+    distance(a, b, 0)
+
+proc ratio*(a, b: string): float =
+    ## Compute similarity of two strings.
+    ##
+    ## The similarity is a number between 0 and 1, it's usually equal or somewhat higher than
+    ## Python's ``difflib.SequenceMatcher.ratio()``, because it's based on real minimal edit
+    ## distance.
+    runnableExamples:
+        from math import round
+        assert round(ratio("Hello world!", "Holly grail!"), 4) == 0.5833
+        assert ratio("Brian", "Jesus") == 0.0
+    let lensum = len(a) + len(b)
+    if lensum == 0:
+        return 1.0
+    let ldist = distance(a, b, 1)
+    result = (lensum - ldist).float / lensum.float
+
+proc hamming*(a, b: string): int =
+    ## Compute Hamming distance of two strings.
+    ##
+    ## The Hamming distance is simply the number of differing characters. That means the length of
+    ## the strings must be the same.
+    runnableExamples:
+        assert hamming("Hello world!", "Holly grail!") == 7
+        assert hamming("Brian", "Jesus") == 5
+    if len(a) != len(b):
+        raise newException(Exception, "expected two strings of the same length")
+    hammingDistance(a, b)
+
+proc jaro*(a, b: string): float =
+    ## Compute Jaro string similarity metric of two strings.
+    ##
+    ## The Jaro string similarity metric is intended for short strings like personal last names. It
+    ## is 0 for completely different strings and 1 for identical strings.
+    runnableExamples:
+        from math import round
+        assert jaro("Brian", "Jesus") == 0.0
+        assert round(jaro("Thorkel", "Thorgier"), 4) == 0.7798
+        assert round(jaro("Dinsdale", "D"), 4) == 0.7083
+    jaroRatio(a, b)
+
+proc jaroWinkler*(a, b: string, prefixWeight: float = 0.1): float =
+    ## Compute Jaro string similarity metric of two strings.
+    ##
+    ## The Jaro-Winkler string similarity metric is a modification of Jaro metric giving more weight
+    ## to common prefix, as spelling mistakes are more likely to occur near ends of words.
+    ##
+    ## The prefix weight is inverse value of common prefix length sufficient to consider the strings
+    ## *identical*. If no prefix weight is specified, 1/10 is used.
+    runnableExamples:
+        from math import round
+        assert jaroWinkler("Brian", "Jesus") == 0.0
+        assert round(jaroWinkler("Thorkel", "Thorgier"), 4) == 0.8679
+        assert round(jaroWinkler("Dinsdale", "D"), 4) == 0.7375
+        assert jaroWinkler("Thorkel", "Thorgier", 0.25) == 1.0
+    if prefixWeight < 0:
+        raise newException(Exception, "negative prefix weight")
+    jaroWinklerRatio(a, b, prefixWeight)
+
+template medianCommon(f: typed, strings: seq[string], weights: seq[float] = @[]): string =
+    if len(strings) == 0:
+        return ""
+
+    var wl = weights
+    if len(wl) == 0:
+        setLen(wl, len(strings))
+        for i in 0..<len(wl):
+            wl[i] = 1.0
+    else:
+        if len(strings) != len(weights):
+            raise newException(Exception, "expected same amount of strings and weights")
+
+    f(strings, wl)
+
+proc median*(strings: seq[string], weights: seq[float] = @[]): string =
+    ## Find an approximate generalized median string using greedy algorithm.
+    ##
+    ## You can optionally pass a weight for each string as the second argument. The weights are
+    ## interpreted as item multiplicities, although any non-negative real numbers are accepted. Use
+    ## them to improve computation speed when strings often appear multiple times in the sequence.
+    runnableExamples:
+        assert median(@["SpSm", "mpamm", "Spam", "Spa", "Sua", "hSam"]) == "Spam"
+        let fixme = @["Levnhtein", "Leveshein", "Leenshten",
+                      "Leveshtei", "Lenshtein", "Lvenstein",
+                      "Levenhtin", "evenshtei"]
+        assert median(fixme) == "Levenshtein"
+    medianCommon(greedyMedian, strings, weights)
+
+proc medianImprove*(s: string, strings: seq[string], weights: seq[float] = @[]): string =
+    ## Improve an approximate generalized median string by perturbations.
+    ##
+    ## The first argument is the estimated generalized median string you want to improve, the others
+    ## are the same as in `median()`. It returns a string with total distance less or equal to that
+    ## of the given string.
+    ##
+    ## Note this is much slower than `median()`. Also note it performs only one improvement step,
+    ## calling `medianImprove()` again on the result may improve it further, though this is unlikely
+    ## to happen unless the given string was not very similar to the actual generalized median.
+    runnableExamples:
+        let fixme = @["Levnhtein", "Leveshein", "Leenshten",
+                      "Leveshtei", "Lenshtein", "Lvenstein",
+                      "Levenhtin", "evenshtei"]
+        assert medianImprove("spam", fixme) == "enhtein"
+        assert medianImprove(medianImprove("spam", fixme), fixme) == "Levenshtein"
+    if len(strings) == 0:
+        return ""
+
+    var wl = weights
+    if len(wl) == 0:
+        setLen(wl, len(strings))
+        for i in 0..<len(wl):
+            wl[i] = 1.0
+    else:
+        if len(strings) != len(weights):
+            raise newException(Exception, "expected same amount of strings and weights")
+
+    wrapper.medianImprove(s, strings, wl)
+
+proc quickmedian*(strings: seq[string], weights: seq[float] = @[]): string =
+    ## Find a very approximate generalized median string, but fast.
+    ##
+    ## See `median()` for argument description.
+    ##
+    ## This method is somewhere between `setmedian()` and picking a random string from the set; both
+    ## speedwise and quality-wise.
+    runnableExamples:
+        let fixme = @["Levnhtein", "Leveshein", "Leenshten",
+                      "Leveshtei", "Lenshtein", "Lvenstein",
+                      "Levenhtin", "evenshtei"]
+        assert quickmedian(fixme) == "Levnshein"
+    medianCommon(wrapper.quickMedian, strings, weights)
+
+proc setmedian*(strings: seq[string], weights: seq[float] = @[]): string =
+    ## Find set median of a string set (passed as a sequence).
+    ##
+    ## See `median()` for argument description.
+    ##
+    ## The returned string is always one of the strings in the sequence.
+    runnableExamples:
+        assert setmedian(@["ehee", "cceaes", "chees", "chreesc",
+                           "chees", "cheesee", "cseese", "chetese"]) == "chees"
+    medianCommon(wrapper.setMedian, strings, weights)
+
+template setSeqCommon(f: typed, a: seq[string], b: seq[string]): float =
+    let lensum = len(a) + len(b)
+
+    if lensum == 0:
+        return 1.0
+
+    if len(a) == 0 or len(b) == 0:
+        return 0.0
+
+    let r = f(a, b)
+
+    if r < 0.0:
+        raise newException(Exception, "failed")
+
+    (lensum.float - r) / lensum.float
+
+proc seqratio*(a: seq[string], b: seq[string]): float =
+    ## Compute similarity ratio of two sequences of strings.
+    ##
+    ## This is like `ratio()`, but for string sequences. A kind of `ratio()` is used to to measure
+    ## the cost of item change operation for the strings.
+    runnableExamples:
+        from math import round
+        assert round(seqratio(@["newspaper", "litter bin", "tinny", "antelope"],
+            @["caribou", "sausage", "gorn", "woody"]), 4) == 0.2152
+        assert seqratio(@[], @["foobar"]) == 0.0
+        assert seqratio(@["foobar"], @[]) == 0.0
+    setSeqCommon(editSeqDistance, a, b)
+
+proc setratio*(a: seq[string], b: seq[string]): float =
+    ## Compute similarity ratio of two strings sets (passed as sequences).
+    ##
+    ## The best match between any strings in the first set and the second set (passed as sequences)
+    ## is attempted. I.e., the order doesn't matter here.
+    runnableExamples:
+        from math import round
+        assert round(setratio(@["newspaper", "litter bin", "tinny", "antelope"],
+            @["caribou", "sausage", "gorn", "woody"]), 4) == 0.2818
+        assert setratio(@[], @["foobar"]) == 0.0
+        assert setratio(@["foobar"], @[]) == 0.0
+    setSeqCommon(setDistance, a, b)
+
+proc editops*(string1: string, string2: string): seq[EditOp] =
+    ## Find sequence of edit operations transforming one string to another.
+    ##
+    ## The result is a sequence of `EditOp` objects. These are operations on single characters.
+    ## In fact the returned sequence doesn't contain the *equal*, but all the related functions
+    ## accept both lists with and without *equals*.
+    runnableExamples:
+        let ops = editops("spam", "park")
+        assert ops[0] == EditOp(`type`: EditType.Delete, spos: 0, dpos: 0)
+        assert ops[1] == EditOp(`type`: EditType.Insert, spos: 3, dpos: 2)
+        assert ops[2] == EditOp(`type`: EditType.Replace, spos: 3, dpos: 3)
+    wrapper.editops(string1, string2)
+
+proc editops*(ops: seq[OpCode], aLen: int, bLen: int): seq[EditOp] =
+    ## Can be used for conversion from `OpCode` to `EditOp`. You can either pass in strings or
+    ## their lengths, the result is the same.
+    checkErrors(aLen, bLen, ops)
+    toEditOps(ops, false)
+
+proc editops*(ops: seq[OpCode], a: string, b: string): seq[EditOp] =
+    ## Can be used for conversion from `OpCode` to `EditOp`. You can either pass in strings or
+    ## their lengths, the result is the same.
+    editops(ops, len(a), len(b))
+
+proc opcodes*(a, b: string): seq[OpCode] =
+    ## Find sequence of edit operations transforming one string to another.
+    ##
+    ## The result is a sequence of `OpCode` objects.
+    runnableExamples:
+        let ops = opcodes("spam", "park")
+        assert ops[0] == OpCode(`type`: EditType.Delete, sbeg: 0, send: 1, dbeg: 0, dend: 0)
+        assert ops[1] == OpCode(`type`: EditType.Keep, sbeg: 1, send: 3, dbeg: 0, dend: 2)
+        assert ops[2] == OpCode(`type`: EditType.Insert, sbeg: 3, send: 3, dbeg: 2, dend: 3)
+        assert ops[3] == OpCode(`type`: EditType.Replace, sbeg: 3, send: 4, dbeg: 3, dend: 4)
+    editops(a, b).toOpCodes(len(a), len(b))
+
+proc opcodes*(ops: seq[EditOp], aLen: int, bLen: int): seq[OpCode] =
+    ## Can be used for conversion from `EditOp` to `OpCode`. You can either pass in strings or
+    ## their lengths, the result is the same.
+    checkErrors(aLen, bLen, ops)
+    ops.toOpCodes(aLen, bLen)
+
+proc opcodes*(ops: seq[EditOp], a: string, b: string): seq[OpCode] =
+    ## Can be used for conversion from `EditOp` to `OpCode`. You can either pass in strings or
+    ## their lengths, the result is the same.
+    opcodes(ops, len(a), len(b))
+
+proc inverse*(ops: seq[EditOp]): seq[EditOp] =
+    ## Invert the sense of an edit operation sequence.
+    ##
+    ## In other words, it returns a sequence of edit operations transforming the second
+    ## (destination) string to the first (source). It can be used with both editops and opcodes.
+    runnableExamples:
+        let inv = inverse(editops("spam", "park"))
+        assert inv[0] == EditOp(`type`: EditType.Insert, spos: 0, dpos: 0)
+        assert inv[1] == EditOp(`type`: EditType.Delete, spos: 2, dpos: 3)
+        assert inv[2] == EditOp(`type`: EditType.Replace, spos: 3, dpos: 3)
+        assert editops("park", "spam") == inv
+    result = ops
+    result.invert()
+
+proc inverse*(ops: seq[OpCode]): seq[OpCode] =
+    ## Invert the sense of an edit operation sequence.
+    ##
+    ## In other words, it returns a sequence of edit operations transforming the second
+    ## (destination) string to the first (source). It can be used with both editops and opcodes.
+    result = ops
+    result.invert()
+
+proc applyEdit*(ops: seq[EditOp], a: string, b:string): string =
+    ## Apply a sequence of edit operations to a string.
+    ##
+    ## In the case of editops, the sequence can be arbitrary ordered subset of the edit sequence
+    ## transforming source string to destination string.
+    runnableExamples:
+        let ops = editops("man", "scotsman")
+        assert applyEdit(ops, "man", "scotsman") == "scotsman"
+        assert applyEdit(ops[0..2], "man", "scotsman") == "scoman"
+    if len(ops) == 0:
+        return a
+    checkErrors(len(a), len(b), ops)
+    apply(a, b, ops)
+
+proc applyEdit*(ops: seq[OpCode], a: string, b:string): string =
+    if len(ops) == 0:
+        return a
+    checkErrors(len(a), len(b), ops)
+    apply(a, b, ops)
+
+template matchingBlocksCommon(ops: typed, aLen: int, bLen: int) =
+    checkErrors(aLen, bLen, ops)
+    result = matchingBlocks(aLen, bLen, ops)
+    result.add(MatchingBlock(spos: aLen, dpos: bLen, len: 0))
+
+proc matchingBlocks*(ops: seq[EditOp], aLen: int, bLen: int): seq[MatchingBlock] =
+    ## Find identical blocks in two strings.
+    ##
+    ## The result is a sequence of `MatchingBlock` objects. It can be used with both editops and
+    ## opcodes. The second and third arguments don't have to be actually strings, their lengths are
+    ## enough.
+    runnableExamples:
+        let (a, b) = ("spam", "park")
+        let mb = matchingBlocks(editops(a, b), a, b)
+        assert mb[0] == MatchingBlock(spos: 1, dpos: 0, `len`: 2)
+        ## The last zero-length block is not an error, but it's there for compatibility with Pythons
+        ## `difflib` which always emits it.
+        assert mb[1] == MatchingBlock(spos: 4, dpos: 4, `len`: 0)
+        assert mb == matchingBlocks(editops(a, b), len(a), len(b))
+    runnableExamples:
+        ## One can join the matching blocks to get two identical strings:
+        from sequtils import map
+        from strutils import join
+        let (a, b) = ("dog kennels", "mattresses")
+        let mb = matchingBlocks(editops(a, b), a, b)
+        assert join(map(mb, proc (x: MatchingBlock): string =
+            a[x.spos ..< x.spos + x.len])) == "ees"
+        assert join(map(mb, proc (x: MatchingBlock): string =
+            b[x.dpos ..< x.dpos + x.len])) == "ees"
+    matchingBlocksCommon(ops, aLen, bLen)
+
+proc matchingBlocks*(ops: seq[EditOp], a: string, b: string): seq[MatchingBlock] =
+    matchingBlocksCommon(ops, len(a), len(b))
+
+proc matchingBlocks*(ops: seq[OpCode], aLen: int, bLen: int): seq[MatchingBlock] =
+    matchingBlocksCommon(ops, aLen, bLen)
+
+proc matchingBlocks*(ops: seq[OpCode], a: string, b: string): seq[MatchingBlock] =
+    matchingBlocksCommon(ops, len(a), len(b))
+
+proc subtractEdit*(ops: seq[EditOp], subsequence: seq[EditOp]): seq[EditOp] =
+    ## Subtract an edit subsequence from a sequence.
+    ##
+    ## The result is equivalent to ``editops(applyEdit(subsequence, s1, s2), s2)``, except that is
+    ## constructed directly from the edit operations. That is, if you apply it to the result of
+    ## subsequence application, you get the same final string as from application of complete `ops`.
+    ## It may be not identical, though (in ambiguous cases, like insertion of a character next to
+    ## the same character).
+    ##
+    ## The subtracted subsequence must be an ordered subset of `ops`.
+    ##
+    ## Note this function does not accept difflib-style opcodes as no one in his right mind wants to
+    ## create subsequences from them.
+    runnableExamples:
+        let e = editops("man", "scotsman")
+        let e1 = e[0..2]
+        let bastard = applyEdit(e1, "man", "scotsman")
+        assert bastard == "scoman"
+        assert applyEdit(subtractEdit(e, e1), bastard, "scotsman") == "scotsman"
+    subtract(ops, subsequence)