sffuzzy

Simple fast fuzzy

Fuzzy library written in go.

This library is a simple fuzzy search with unicode normalization and an arbitrary score system.

Test the library

git clone https://github.com/eregnier/sffuzzy
cd ssfuzzy
make test-trace

Usage

go get github.com/eregnier/sffuzzy

Usage samples are in test.go

A minimal usage code below:

  //One shot search
  names := []string{"super man", "super noel", "super du"}
  results := fuzzy.SearchOnce("perdu", &names, fuzzy.Options{Sort: true, Limit: 5, Normalize: true})

  //Use search cache for performance
  names := []string{"super man", "super noel", "super du"}
  options := fuzzy.Options{Sort: true, Limit: 5, Normalize: true}
  cacheTargets := fuzzy.Prepare(&names, options)
  results := fuzzy.Search("perdu", cacheTargets, options)

Options

  options := fuzzy.Options{Sort: true, Normalize: true, Limit: 10}

This options structure have the following options

Performances

The given sample file is a flat csv loaded as string list.

Multi thread performances are worse with my code, so I reverted

On a AMD 3600x and on a single core I fuzzy search a text in 40 ms in SearchOnce mode

When I build cache with a Prepare(data *[]string), and then I run a Search, the prepare takes about 36ms and the Search about 4ms on the data sample of ~155K lines for 320Ko.

Execution

The following code test.go

Have the following output

2020/04/29 02:07:57 TestMinimalSearch &{[{super du 8 5 1} {super man 3 3 4} {super noel 3 3 5}] 8}
2020/04/29 02:07:57 TestMinimalSearchCache &{[{super du 8 5 1} {super man 3 3 4} {super noel 3 3 5}] 8}
2020/04/29 02:07:57  + Cache search, first search is slower.
2020/04/29 02:07:57  🕑 Duration: 9.435114ms
2020/04/29 02:07:57  + Cached searches
2020/04/29 02:07:57  🕑 Duration: 3.883137ms
2020/04/29 02:07:57 [{San Francisco;United States 13 10 16} {South San Francisco;United States 12 10 22} {St. Francis;United States 12 10 19}]
2020/04/29 02:07:57  🕑 Duration: 2.100023ms
2020/04/29 02:07:57 [{Mumbai;India 11 6 0} {Mumbwa;Zambia 8 6 6} {Mount Gambier;Australia 8 6 16}]
2020/04/29 02:07:57  🕑 Duration: 3.992907ms
2020/04/29 02:07:57 [{Hong Kong;Hong Kong 16 8 0} {Xiangkhoang;Laos 13 8 3} {Mokhotlong;Lesotho 12 8 7}]
2020/04/29 02:07:57  🕑 Duration: 2.312343ms
2020/04/29 02:07:57 [{Agadez;Niger 11 6 0} {Várzea Grande;Brazil 8 6 7} {Altagracia de Orituco;Venezuela 8 6 21}]
2020/04/29 02:07:57  🕑 Duration: 2.034594ms
2020/04/29 02:07:57 [{Palmas;Brazil 10 5 0} {La Palma;Panama 10 5 0} {Las Palmas de Gran Canaria;Spain 10 5 0}]
2020/04/29 02:07:57  🕑 Duration: 4.029126ms
2020/04/29 02:07:57 [{Sucre;Bolivia 20 12 0} {Quime;Bolivia 13 7 0} {Villazón;Bolivia 13 7 0}]
2020/04/29 02:07:57  🕑 Duration: 3.910717ms
2020/04/29 02:07:57 [{Ibb;Yemen 16 8 0} {Ibb;Yemen 16 8 0} {Dhamār;Yemen 11 5 0}]
2020/04/29 02:07:57  🕑 Duration: 3.826816ms
2020/04/29 02:07:57 [{West View;United States 16 8 0} {Westview;United States 16 8 0} {Viera West;United States 14 8 3}]
2020/04/29 02:07:57  + Search all at once
2020/04/29 02:07:57  🕑 Duration: 44.714400ms
2020/04/29 02:07:57 Print plain unmarshaled json results
2020/04/29 02:07:57 [
  {
    "target": "Ōsaka;Japan",
    "score": 13,
    "matchCount": 10,
    "typos": 1
  },
  {
    "target": "Northwest Harborcreek;United States",
    "score": 5,
    "matchCount": 5,
    "typos": 29
  },
  {
    "target": "Oshakati;Namibia",
    "score": 5,
    "matchCount": 5,
    "typos": 11
  },
  {
    "target": "Colombo;Sri Lanka",
    "score": 5,
    "matchCount": 5,
    "typos": 11
  },
  {
    "target": "Coxsackie;United States",
    "score": 5,
    "matchCount": 5,
    "typos": 17
  }
]
PASS
ok  	_/home/utopman/sources/sffuzzy	0.083s

The cli

There is a simple cli bundled with this library which usage is in the executable help

go run cli.go --help
Usage: cli [--limit LIMIT] [--sort] [--normalize] SEARCH

Positional arguments:
  SEARCH                 Search terms to find in given data

Options:
  --limit LIMIT, -l LIMIT
                         Results limit, use -1 for no limit [default: 10]
  --sort, -s             Whether or not results are sorted [default: true]
  --normalize, -n        normalize search string and data string for searching. It fuzzy search with no accents/special characters [default: true]
  --help, -h             display this help and exit

Here is a sample about how to use it from this repository sources

head ../sample.csv | go run cli.go -s=1 -l=3 "kol"
[
  {
    "target": "Kolkata;India",
    "score": 8,
    "matchCount": 3,
    "typos": 0
  },
  {
    "target": "Tokyo;Japan",
    "score": 2,
    "matchCount": 2,
    "typos": 7
  },
  {
    "target": "Mexico City;Mexico",
    "score": 2,
    "matchCount": 0,
    "typos": 0
  }
]

It just takes a flat newline separated database to query in stdin. Then it returns the json results as raw indented json depending on given query string and parameters

Licence

MIT