edit-distance 0.1 → 0.1.1
raw patch · 3 files changed
+78/−45 lines, 3 filesdep +test-frameworkPVP ok
version bump matches the API change (PVP)
Dependencies added: test-framework
API changes (from Hackage documentation)
Files
- README.textile +49/−0
- Text/EditDistance/Tests.hs +3/−26
- edit-distance.cabal +26/−19
+ README.textile view
@@ -0,0 +1,49 @@+h1. Edit Distance Algorithms + +You can help improve this README with extra snippets and advice by using the "GitHub wiki":http://github.com/batterseapower/edit-distance/wikis/readme. + + +h2. Installing + +To just install the library: + +<pre> +<code>runghc Setup.lhs configure +runghc Setup.lhs build +sudo runghc Setup.lhs install +</pre> +</code> + +If you want to build the tests, to check it's all working: + +<pre> +<code>runghc Setup.lhs configure -ftests +runghc Setup.lhs build +dist/build/edit-distance-tests/edit-distance-tests +</pre> +</code> + + +h2. Description + +Edit distances algorithms for fuzzy matching. Specifically, this library provides: + +* "Levenshtein distance":http://en.wikipedia.org/wiki/Levenshtein_distance +* "Restricted Damerau-Levenshtein distance":http://en.wikipedia.org/wiki/Damerau-Levenshtein_distance + +They have been fairly heavily optimized. Indeed, for situations where one of the strings is under 32 characters long I use a rather neat "bit vector" algorithm: see "the authors paper":http://www.cs.uta.fi/~helmu/pubs/psc02.pdf and "the associated errata":[http://www.cs.uta.fi/~helmu/pubs/PSCerr.html for more information. The algorithms __could__ be faster, but they aren't yet slow enough to force me into improving the situation. + + +h2. Example + +<pre> +<code>Text.EditDistance> levenshteinDistance defaultEditCosts "witch" "kitsch" +2</code> +</pre> + + +h2. Linkage + +* "Hackage":http://hackage.haskell.org/cgi-bin/hackage-scripts/package/edit-distance +* "Bug Tracker":http://bsp.lighthouseapp.com/projects/14822-hs-edit-distance +* "GitHub":http://github.com/batterseapower/edit-distance
Text/EditDistance/Tests.hs view
@@ -1,34 +1,11 @@ module Main where -import Text.EditDistance.Tests.Framework import Text.EditDistance.Tests.Properties -import System.Environment-import System.Exit-import System.Random-import Test.QuickCheck+import Test.Framework +import Data.Monoid -testConfig :: Config-testConfig | True = defaultConfig { configMaxTest = 1000 }- | otherwise = defaultConfig main :: IO ()-main = do- args <- getArgs- (rnd, seed) <- case args of - [] -> mkStdGenWithKnownSeed- [old_seed] -> let seed = read old_seed- in return (mkStdGen seed, seed)- _ -> error $ "Unrecognised arguments " ++ unwords args- - putStrLn $ "Running tests with seed " ++ show seed- result <- runTests testConfig rnd tests- exitWith $ if result- then ExitSuccess- else ExitFailure 1--mkStdGenWithKnownSeed :: IO (StdGen, Int)-mkStdGenWithKnownSeed = do- seed <- randomIO- return (mkStdGen seed, seed)+main = defaultMain $ map (plusTestOptions $ mempty { topt_maximum_generated_tests = Just 1000 }) tests
edit-distance.cabal view
@@ -1,19 +1,25 @@-Name: edit-distance-Version: 0.1-Cabal-Version: >= 1.2-Category: Algorithms-Synopsis: Levenhstein and restricted Damerau-Levenshtein edit distances-Description: Optimized edit distances for fuzzy matching, including Levenhstein and restricted Damerau-Levenshtein algorithms.-License: BSD3-License-File: LICENSE-Author: Max Bolingbroke-Maintainer: batterseapower@hotmail.com-Build-Type: Simple+Name: edit-distance+Version: 0.1.1+Cabal-Version: >= 1.2+Category: Algorithms+Synopsis: Levenshtein and restricted Damerau-Levenshtein edit distances+Description: Optimized edit distances for fuzzy matching, including Levenshtein and restricted Damerau-Levenshtein algorithms.+License: BSD3+License-File: LICENSE+Extra-Source-Files: README.textile+Author: Max Bolingbroke+Maintainer: batterseapower@hotmail.com+Homepage: http://github.com/batterseapower/edit-distance+Build-Type: Simple Flag Tests- Description: Enable building the tests and benchmark suite+ Description: Enable building the tests Default: False +Flag Benchmark+ Description: Enable building the benchmark suite+ Default: False+ Flag SplitBase Description: Choose the new smaller, split-up base package Default: True@@ -26,6 +32,7 @@ Text.EditDistance.STUArray Text.EditDistance.Bits Text.EditDistance.MonadUtilities+ if flag(splitBase) Build-Depends: base >= 3, array >= 0.1, random >= 1.0, containers >= 0.1.0.1 else@@ -35,15 +42,14 @@ Executable edit-distance-tests Main-Is: Text/EditDistance/Tests.hs+ + Build-Depends: test-framework >= 0.1.1, QuickCheck >= 1.1 if flag(splitBase)- Build-Depends: base >= 3, array >= 0.1, random >= 1.0,- QuickCheck >= 1.1+ Build-Depends: base >= 3, array >= 0.1, random >= 1.0 else- Build-Depends: base < 3, - QuickCheck >= 1.1+ Build-Depends: base < 3 - Extensions: PatternGuards, PatternSignatures, - RankNTypes, ExistentialQuantification,+ Extensions: PatternGuards, PatternSignatures, ScopedTypeVariables Ghc-Options: -O2 -fvia-C -Wall -fno-warn-orphans @@ -52,6 +58,7 @@ Executable edit-distance-benchmark Main-Is: Text/EditDistance/Benchmark.hs+ if flag(splitBase) Build-Depends: base >= 3, array >= 0.1, random >= 1.0, old-time >= 1.0, process >= 1.0, parallel >= 1.0, unix >= 2.3@@ -61,5 +68,5 @@ Ghc-Options: -O2 -fvia-C -Wall - if !flag(tests)+ if !flag(benchmark) Buildable: False