c-cube / spelll Goto Github PK

View Code? Open in Web Editor NEW

24.0 5.0 3.0 136 KB

fuzzy string searching, using Levenshtein automaton. Can be used for spell-checking.

Home Page: http://c-cube.github.io/spelll/

License: BSD 2-Clause "Simplified" License

OCaml 99.30% Makefile 0.70%

levenshtein-automaton ocaml spell-check

spelll's Introduction

Spelll

Fuzzy string searching, using Levenshtein automaton. Can be used for spell-checking.

API documentation can be found here, and the source code here.

Some examples:

# #require "spelll";;
# let dfa = Spelll.of_string ~limit:1 "hello";;
val dfa : Spelll.automaton = <abstr>
# Spelll.match_with dfa "hell";;
- : bool = true
# Spelll.match_with dfa "hall";;
- : bool = false
# let idx = Spelll.Index.of_list ["hello", "world"; "hall", "vestibule"];;
val idx : string Spelll.Index.t = <abstr>
# Spelll.Index.retrieve_l idx ~limit:1 "hell" ;;
- : string list = ["world"; "vestibule"]
# Spelll.Index.retrieve_l idx ~limit:1 "hall" ;;
- : string list = ["vestibule"]

License

This software is free, under the BSD-2 license. See the LICENSE file.

Build

You only need OCaml (>= 4.02 should be enough) and dune and seq. Type

$ make
$ make install

spelll's People

Contributors

Stargazers

Watchers

Forkers

gbury rgrinberg kit-ty-kate

spelll's Issues

inconsistent example

Hi, the library looks nice, but the example is very confusing

# let idx = Spelll.Index.of_list ["hello", "world"; "hall", "vestibule"];;
val idx : string Spelll.Index.t = <abstr>
# Spelll.Index.retrieve_l idx ~limit:1 "hell" ;;
- : string list = ["world"; "vestibule"]
# Spelll.Index.retrieve_l idx ~limit:1 "hall" ;;
- : string list = ["vestibule"]

Current online doc (at https://cedeela.fr/~simon/software/spelll/Spelll.html), seems out of sync with the implementation. For instance, the online doc says say Spelll includes Spelll.S but without mentioning the type equalities that makes it usable.

handle transpositions in the metric

See https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance , at least for the edit_distance part (not sure if the automaton will accept).

use `Seq` in the API

use ocaml-mdx for testing the readme

also use containers to test, not batteries

minor release with API change and `bin_annot`

install the .cmt{,i} files, the improved doc, etc.
Also, the API of remove changed.

Stack overflow

Hi, when using spelll on, admittedly, very big maps, I seem to get stack overflows when trying to retrieve some elements. Here is the relevant part of the backtrace:

Stack overflow
        Raised by primitive operation at file "src/Spelll.ml", line 253, characters 22-40
        Called from file "set.ml", line 348, characters 18-35
        Called from file "map.ml", line 123, characters 18-33
        Called from file "map.ml", line 130, characters 21-33
        Called from file "map.ml", line 130, characters 21-33
        Called from file "map.ml", line 130, characters 21-33
        Called from file "map.ml", line 130, characters 21-33
        Called from file "src/Spelll.ml", line 375, characters 18-47
        Called from file "src/Spelll.ml", line 390, characters 24-49
        Called from file "list.ml", line 110, characters 12-15
        Called from file "src/Spelll.ml", line 353, characters 6-305
        Called from file "list.ml", line 110, characters 12-15
        Called from file "src/Spelll.ml", line 353, characters 6-305
        Called from file "list.ml", line 110, characters 12-15
        Called from file "src/Spelll.ml", line 353, characters 6-305
        Called from file "list.ml", line 110, characters 12-15
        Called from file "src/Spelll.ml", line 353, characters 6-305
        Called from file "list.ml", line 110, characters 12-15
        Called from file "src/Spelll.ml", line 353, characters 6-305
        Called from file "list.ml", line 110, characters 12-15
        Called from file "src/Spelll.ml", line 353, characters 6-305
        Called from file "list.ml", line 110, characters 12-15
        Called from file "src/Spelll.ml", line 353, characters 6-305
        Called from file "list.ml", line 110, characters 12-15
        Called from file "src/Spelll.ml", line 353, characters 6-305
        Called from file "list.ml", line 110, characters 12-15
        Called from file "src/Spelll.ml", line 353, characters 6-305
        Called from file "src/Spelll.ml", line 408, characters 6-33
        Called from file "src/Spelll.ml" (inlined), line 442, characters 14-28
        Called from file "src/Spelll.ml", line 543, characters 16-34

This is using version 0.3 on ocaml 4.08.1