text-metrics 0.1.0 → 0.2.0
raw patch · 8 files changed
+238/−25 lines, 8 filesdep ~criteriondep ~text-metrics
Dependency ranges changed: criterion, text-metrics
Files
- CHANGELOG.md +7/−0
- Data/Text/Metrics.hs +80/−1
- README.md +17/−4
- bench/Main.hs +3/−1
- cbits/text_metrics.c +87/−16
- cbits/text_metrics.h +7/−0
- tests/Main.hs +34/−0
- text-metrics.cabal +3/−3
CHANGELOG.md view
@@ -1,3 +1,10 @@+## Text Metrics 0.2.0++* Made the `levenshtein`, `levenshteinNorm`, `damerauLevenshtein`, and+ `demerauLevenshtein` more efficient.++* Added `jaro` and `jaroWinkler` functions.+ ## Text Metrics 0.1.0 * Initial release.
Data/Text/Metrics.hs view
@@ -11,6 +11,20 @@ -- It works with strict 'Text' values and returns either 'Natural' numbers -- (because the metrics cannot be negative), or @'Ratio' 'Natural'@ values -- because returned values are rational non-negative numbers by definition.+--+-- The functions provided here are the fastest implementations available for+-- use in Haskell programs. In fact the functions are implemented in C for+-- maximal efficiency, but this leads to a minor flaw. When we work with+-- 'Text' values in C, they are represented as UTF-16 encoded strings of+-- two-byte values. The algorithms treat the strings as if a character+-- corresponds to one element in such strings, which is true for almost all+-- modern text data. However, there are characters that are represented by+-- two adjoined elements in UTF-16: emoji, historic scripts, less used+-- Chinese ideographs, and some more. If input 'Text' of the functions+-- contains such characters, the functions may return slightly incorrect+-- result. Decide for yourself if this is acceptable for your use case, but+-- chances are you will never run into situations when the functions produce+-- incorrect results. {-# LANGUAGE CPP #-} {-# LANGUAGE ForeignFunctionInterface #-}@@ -23,7 +37,9 @@ , damerauLevenshtein , damerauLevenshteinNorm -- * Other- , hamming )+ , hamming+ , jaro+ , jaroWinkler ) where import Data.Ratio@@ -111,6 +127,69 @@ foreign import ccall unsafe "tmetrics_hamming" c_hamming :: CUInt -> Ptr Word16 -> Ptr Word16 -> IO CUInt++-- | Return Jaro distance between two 'Text' values. Returned value is in+-- range from 0 (no similarity) to 1 (exact match).+--+-- While the algorithm is pretty clear for artificial examples (like those+-- from the linked Wikipedia article), for /arbitrary/ strings, it may be+-- hard to decide which of two strings should be considered as one having+-- “reference” order of characters (since order of matching characters in an+-- essential part of the definition of the algorithm). This makes us+-- consider the first string the “reference” string (with correct order of+-- characters). Thus generally,+--+-- > jaro a b ≠ jaro b a+--+-- This asymmetry can be found in all implementations of the algorithm on+-- the internet, AFAIK.+--+-- See also: <http://en.wikipedia.org/wiki/Jaro%E2%80%93Winkler_distance>+--+-- @since 0.2.0++jaro :: Text -> Text -> Ratio Natural+jaro = jaroCommon (\_ _ _ _ x -> return x)++jaroCommon :: (CUInt -> Ptr Word16 -> CUInt -> Ptr Word16 -> Ratio Natural -> IO (Ratio Natural)) -> Text -> Text -> Ratio Natural+jaroCommon f a b = unsafePerformIO $ alloca $ \m' -> alloca $ \t' ->+ TF.useAsPtr a $ \aptr asize ->+ TF.useAsPtr b $ \bptr bsize ->+ if asize == 0 || bsize == 0+ then return (1 % 1)+ else do+ let asize' = fromIntegral asize+ bsize' = fromIntegral bsize+ c_jaro m' t' asize' aptr bsize' bptr+ m <- fromIntegral <$> peek m'+ t <- fromIntegral <$> peek t'+ f asize' aptr bsize' bptr $+ if m == 0+ then 0+ else ((m % fromIntegral asize) ++ (m % fromIntegral bsize) ++ ((m - t) % m)) / 3+{-# INLINE jaroCommon #-}++foreign import ccall unsafe "tmetrics_jaro"+ c_jaro :: Ptr CUInt -> Ptr CUInt -> CUInt -> Ptr Word16 -> CUInt -> Ptr Word16 -> IO ()++-- | Return Jaro-Winkler distance between two 'Text' values. Returned value+-- is in range from 0 (no similarity) to 1 (exact match).+--+-- See also: <http://en.wikipedia.org/wiki/Jaro%E2%80%93Winkler_distance>+--+-- @since 0.2.0++jaroWinkler :: Text -> Text -> Ratio Natural+jaroWinkler = jaroCommon g+ where+ g asize aptr bsize bptr dj = do+ l <- fromIntegral <$> c_common_prefix asize aptr bsize bptr+ return (dj + (1 % 10) * l * (1 - dj))++foreign import ccall unsafe "tmetrics_common_prefix"+ c_common_prefix :: CUInt -> Ptr Word16 -> CUInt -> Ptr Word16 -> IO CUInt ---------------------------------------------------------------------------- -- Helpers
README.md view
@@ -12,6 +12,19 @@ (because the metrics cannot be negative), or `Ratio Natural` values because returned values are rational non-negative numbers by definition. +The functions provided here are the fastest implementations available for+use in Haskell programs. In fact the functions are implemented in C for+maximal efficiency, but this leads to a minor flaw. When we work with `Text`+values in C, they are represented as UTF-16 encoded strings of two-byte+values. The algorithms treat the strings as if a character corresponds to+one element in such strings, which is true for almost all modern text data.+However, there are characters that are represented by two adjoined elements+in UTF-16: emoji, historic scripts, less used Chinese ideographs, and some+more. If input `Text` of the functions contains such characters, the+functions may return slightly incorrect result. Decide for yourself if this+is acceptable for your use case, but chances are you will never run into+situations when the functions produce incorrect results.+ The current version of the package implements: * [Levenshtein distance](http://en.wikipedia.org/wiki/Levenshtein_distance)@@ -19,13 +32,13 @@ * [Damerau-Levenshtein distance](http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance) * [Normalized Damerau-Levenshtein distance](http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance) * [Hamming distance](http://en.wikipedia.org/wiki/Hamming_distance)+* [Jaro distance](http://en.wikipedia.org/wiki/Jaro%E2%80%93Winkler_distance)+* [Jaro-Winkler distance](http://en.wikipedia.org/wiki/Jaro%E2%80%93Winkler_distance) TODO list: * [Overlap coefficient](http://en.wikipedia.org/wiki/Overlap_coefficient) * [Jaccard similarity coefficient](http://en.wikipedia.org/wiki/Jaccard_index)-* [Jaro distance](http://en.wikipedia.org/wiki/Jaro%E2%80%93Winkler_distance)-* [Jaro-Winkler distance](http://en.wikipedia.org/wiki/Jaro%E2%80%93Winkler_distance) ## Comparison with the `edit-distance` package @@ -49,11 +62,11 @@ fairly heavily optimized”, which is apparently true, yet the `text-metrics` is faster for short strings (under 64 characters) and even faster for longer strings (scales better). How much faster? For short- strings more than ×2.5, and about ×4 for longer strings.+ strings more than ×3, and about ×4 for longer strings. ## Implementation -All “meat” of the algorithms is written is C in a rather straightforward+All “meat” of the algorithms is written in C in a rather straightforward way. Levenshtein variants are based on the “iterative algorithm with two matrix rows” from Wikipedia with additional improvement that we do not copy current row of distances into previous row, but just swap the pointers
bench/Main.hs view
@@ -44,7 +44,9 @@ , btmetric "levenshteinNorm" levenshteinNorm , btmetric "damerauLevenshtein" damerauLevenshtein , btmetric "damerauLevenshteinNorm" damerauLevenshteinNorm- , btmetric "hamming" hamming ]+ , btmetric "hamming" hamming+ , btmetric "jaro" jaro+ , btmetric "jaroWinkler" jaroWinkler ] -- | Produce benchmark group to test
cbits/text_metrics.c view
@@ -40,11 +40,19 @@ if (la == 0) return lb; if (lb == 0) return la; - unsigned int v_len = lb + 1;- unsigned int *v0 = malloc(sizeof(unsigned int) * v_len);- unsigned int *v1 = malloc(sizeof(unsigned int) * v_len);- unsigned int i, j;+ unsigned int v_len = lb + 1, *v0, *v1, i, j; + if (v_len > VLEN_MAX)+ {+ v0 = malloc(sizeof(unsigned int) * v_len);+ v1 = malloc(sizeof(unsigned int) * v_len);+ }+ else+ {+ v0 = alloca(sizeof(unsigned int) * v_len);+ v1 = alloca(sizeof(unsigned int) * v_len);+ }+ for (i = 0; i < v_len; i++) v0[i] = i; @@ -58,7 +66,7 @@ unsigned int x = *(v1 + j) + 1; unsigned int y = *(v0 + j + 1) + 1; unsigned int z = *(v0 + j) + cost;- *(v1 + j + 1) = x > y ? (y > z ? z : y) : (x > z ? z : x);+ *(v1 + j + 1) = MIN(x, MIN(y, z)); } unsigned int *ptr = v0;@@ -68,8 +76,11 @@ unsigned int result = *(v0 + lb); - free(v0);- free(v1);+ if (v_len > VLEN_MAX)+ {+ free(v0);+ free(v1);+ } return result; }@@ -79,12 +90,21 @@ if (la == 0) return lb; if (lb == 0) return la; - unsigned int v_len = lb + 1;- unsigned int *v0 = malloc(sizeof(unsigned int) * v_len);- unsigned int *v1 = malloc(sizeof(unsigned int) * v_len);- unsigned int *v2 = malloc(sizeof(unsigned int) * v_len);- unsigned int i, j;+ unsigned int v_len = lb + 1, *v0, *v1, *v2, i, j; + if (v_len > VLEN_MAX)+ {+ v0 = malloc(sizeof(unsigned int) * v_len);+ v1 = malloc(sizeof(unsigned int) * v_len);+ v2 = malloc(sizeof(unsigned int) * v_len);+ }+ else+ {+ v0 = alloca(sizeof(unsigned int) * v_len);+ v1 = alloca(sizeof(unsigned int) * v_len);+ v2 = alloca(sizeof(unsigned int) * v_len);+ }+ for (i = 0; i < v_len; i++) v0[i] = i; @@ -98,7 +118,7 @@ unsigned int x = *(v1 + j) + 1; unsigned int y = *(v0 + j + 1) + 1; unsigned int z = *(v0 + j) + cost;- *(v1 + j + 1) = x > y ? (y > z ? z : y) : (x > z ? z : x);+ *(v1 + j + 1) = MIN(x, MIN(y, z)); unsigned int val = *(v2 + j - 1) + cost; if ( i > 0 && j > 0 &&@@ -116,9 +136,12 @@ unsigned int result = *(v0 + lb); - free(v0);- free(v1);- free(v2);+ if (v_len > VLEN_MAX)+ {+ free(v0);+ free(v1);+ free(v2);+ } return result; }@@ -131,6 +154,54 @@ for (i = 0; i < len; i++) { if (*(a + i) != *(b + i)) acc++;+ }+ return acc;+}++void tmetrics_jaro (unsigned int *m, unsigned int *t, unsigned int la, uint16_t *a, unsigned int lb, uint16_t *b)+{+ unsigned int d = 0, i, j, tj = 0, from, to;+ char *v;++ *m = 0, *t = 0;++ if (la >= 2 && lb >= 2)+ d = MAX(lb, la) / 2 - 1;++ if (lb > VLEN_MAX) v = malloc(sizeof(char) * lb);+ else v = alloca(sizeof(char) * lb);++ for (i = 0; i < lb; i++) *(v + i) = 0;++ for (i = 0; i < la; i++)+ {+ from = i < d ? 0 : i - d;+ to = MIN(i + d + 1, lb);+ for (j = from; j < to; j++)+ {+ if (*(v + j)) continue;++ if (*(a + i) == *(b + j))+ {+ if (j < tj) (*t)++;+ else tj = j;+ *(v + j) = 1;+ (*m)++;+ break;+ }+ }+ }++ if (lb > VLEN_MAX) free(v);+}++unsigned int tmetrics_common_prefix (unsigned int la, uint16_t *a, unsigned int lb, uint16_t *b)+{+ unsigned int acc = 0, i, l = MIN(la, lb);+ for (i = 0; i < l; i++)+ {+ if (*(a + i) == *(b + i)) acc++;+ else break; } return acc; }
cbits/text_metrics.h view
@@ -37,6 +37,11 @@ #include <stdint.h> #include <stdlib.h> +#define MAX(a, b) ((a) > (b) ? (a) : (b))+#define MIN(a, b) ((a) < (b) ? (a) : (b))++#define VLEN_MAX 255 /* Up to this length we use alloca. */+ /* Levenshein variants */ unsigned int tmetrics_levenshtein (unsigned int, uint16_t *, unsigned int, uint16_t *);@@ -45,5 +50,7 @@ /* Other */ unsigned int tmetrics_hamming (unsigned int, uint16_t *, uint16_t *);+void tmetrics_jaro (unsigned int *, unsigned int *, unsigned int, uint16_t *, unsigned int, uint16_t *);+unsigned int tmetrics_common_prefix (unsigned int, uint16_t *, unsigned int, uint16_t *); #endif /* TEXT_METRICS_H */
tests/Main.hs view
@@ -101,6 +101,40 @@ testPair hamming "lucky" "lucky" (Just 0) testPair hamming "" "" (Just 0) testPair hamming "small" "big" Nothing+ describe "jaro" $ do+ testPair jaro "aa" "a" (5 % 6)+ testPair jaro "a" "aa" (5 % 6)+ testPair jaro "martha" "marhta" (17 % 18)+ testPair jaro "marhta" "martha" (17 % 18)+ testPair jaro "dwayne" "duane" (37 % 45)+ testPair jaro "duane" "dwayne" (37 % 45)+ testPair jaro "dixon" "dicksonx" (23 % 30)+ testPair jaro "dicksonx" "dixon" (23 % 30)+ testPair jaro "jones" "johnson" (83 % 105)+ testPair jaro "johnson" "jones" (83 % 105)+ testPair jaro "brain" "brian" (14 % 15)+ testPair jaro "brian" "brain" (14 % 15)+ testPair jaro "five" "ten" (0 % 1)+ testPair jaro "ten" "five" (0 % 1)+ testPair jaro "lucky" "lucky" (1 % 1)+ testPair jaro "" "" (1 % 1)+ describe "jaroWinkler" $ do+ testPair jaroWinkler "aa" "a" (17 % 20)+ testPair jaroWinkler "a" "aa" (17 % 20)+ testPair jaroWinkler "martha" "marhta" (173 % 180)+ testPair jaroWinkler "marhta" "martha" (173 % 180)+ testPair jaroWinkler "dwayne" "duane" (21 % 25)+ testPair jaroWinkler "duane" "dwayne" (21 % 25)+ testPair jaroWinkler "dixon" "dicksonx" (61 % 75)+ testPair jaroWinkler "dicksonx" "dixon" (61 % 75)+ testPair jaroWinkler "jones" "johnson" (437 % 525)+ testPair jaroWinkler "johnson" "jones" (437 % 525)+ testPair jaroWinkler "brain" "brian" (71 % 75)+ testPair jaroWinkler "brian" "brain" (71 % 75)+ testPair jaroWinkler "five" "ten" (0 % 1)+ testPair jaroWinkler "ten" "five" (0 % 1)+ testPair jaroWinkler "lucky" "lucky" (1 % 1)+ testPair jaroWinkler "" "" (1 % 1) -- | Test that given function returns the same results when order of -- arguments is swapped.
text-metrics.cabal view
@@ -31,7 +31,7 @@ -- POSSIBILITY OF SUCH DAMAGE. name: text-metrics-version: 0.1.0+version: 0.2.0 cabal-version: >= 1.10 license: BSD3 license-file: LICENSE.md@@ -78,7 +78,7 @@ , base >= 4.7 && < 5.0 , hspec >= 2.0 && < 3.0 , text >= 0.2 && < 1.3- , text-metrics >= 0.1.0+ , text-metrics >= 0.2.0 if !impl(ghc >= 7.10) build-depends: nats == 1.* if flag(dev)@@ -95,7 +95,7 @@ , criterion >= 0.6.2.1 && < 1.2 , deepseq >= 1.4 && < 1.5 , text >= 0.2 && < 1.3- , text-metrics >= 0.1.0+ , text-metrics >= 0.2.0 if !impl(ghc >= 7.10) build-depends: nats == 1.* if flag(dev)