# ![bleve](docs/bleve.png) bleve

[![Tests](https://github.com/blevesearch/bleve/actions/workflows/tests.yml/badge.svg?branch=master&event=push)](https://github.com/blevesearch/bleve/actions/workflows/tests.yml?query=event%3Apush+branch%3Amaster)
[![Coverage Status](https://coveralls.io/repos/github/blevesearch/bleve/badge.svg)](https://coveralls.io/github/blevesearch/bleve)
[![Go Reference](https://pkg.go.dev/badge/github.com/blevesearch/bleve/v2.svg)](https://pkg.go.dev/github.com/blevesearch/bleve/v2)
[![Join the chat](https://badges.gitter.im/join_chat.svg)](https://app.gitter.im/#/room/#blevesearch_bleve:gitter.im)
[![Go Report Card](https://goreportcard.com/badge/github.com/blevesearch/bleve/v2)](https://goreportcard.com/report/github.com/blevesearch/bleve/v2)
[![Sourcegraph](https://sourcegraph.com/github.com/blevesearch/bleve/-/badge.svg)](https://sourcegraph.com/github.com/blevesearch/bleve?badge)
[![License](https://img.shields.io/badge/License-Apache%202.0-blue.svg)](https://opensource.org/licenses/Apache-2.0)

A modern indexing + search library in GO

## Features

* Index any GO data structure or JSON
* Intelligent defaults backed up by powerful configuration ([scorch](https://github.com/blevesearch/bleve/blob/master/index/scorch/README.md))
* Supported field types:
  * `text`, `number`, `datetime`, `boolean`, `geopoint`, `geoshape`, `IP`, `vector`
* Supported query types:
  * `term`, `phrase`, `match`, `match_phrase`, `prefix`, `regexp`, `wildcard`, `fuzzy`
  * term range, numeric range, date range, boolean field
  * compound queries: `conjuncts`, `disjuncts`, boolean (`must`/`should`/`must_not`)
  * [query string syntax](http://www.blevesearch.com/docs/Query-String-Query/)
  * [geo spatial search](https://github.com/blevesearch/bleve/blob/master/geo/README.md)
  * approximate k-nearest neighbors via [vector search](https://github.com/blevesearch/bleve/blob/master/docs/vectors.md)
  * [synonym search](https://github.com/blevesearch/bleve/blob/master/docs/synonyms.md)
  * [hierarchical nested search](https://github.com/blevesearch/bleve/blob/master/docs/hierarchy.md)
* [tf-idf](https://github.com/blevesearch/bleve/blob/master/docs/scoring.md#tf-idf) / [bm25](https://github.com/blevesearch/bleve/blob/master/docs/scoring.md#bm25) scoring models
* Hybrid search: exact + semantic
  * Supports [RRF (Reciprocal Rank Fusion) and RSF (Relative Score Fusion)](docs/score_fusion.md)
* [Result pagination](https://github.com/blevesearch/bleve/blob/master/docs/pagination.md)
* Query time boosting
* Search result match highlighting with document fragments
* Aggregations/faceting support:
  * terms facet
  * numeric range facet
  * date range facet

## Indexing

```go
message := struct {
    Id   string
    From string
    Body string
}{
    Id:   "example",
    From: "xyz@couchbase.com",
    Body: "bleve indexing is easy",
}

mapping := bleve.NewIndexMapping()
index, err := bleve.New("example.bleve", mapping)
if err != nil {
    panic(err)
}
index.Index(message.Id, message)
```

## Querying

```go
index, _ := bleve.Open("example.bleve")
query := bleve.NewQueryStringQuery("bleve")
searchRequest := bleve.NewSearchRequest(query)
searchResult, _ := index.Search(searchRequest)
```

## Command Line Interface

To install the CLI for the latest release of bleve, run:

```bash
go install github.com/blevesearch/bleve/v2/cmd/bleve@latest
```

```text
$ bleve --help
Bleve is a command-line tool to interact with a bleve index.

Usage:
  bleve [command]

Available Commands:
  bulk        bulk loads from newline delimited JSON files
  check       checks the contents of the index
  count       counts the number documents in the index
  create      creates a new index
  dictionary  prints the term dictionary for the specified field in the index
  dump        dumps the contents of the index
  fields      lists the fields in this index
  help        Help about any command
  index       adds the files to the index
  mapping     prints the mapping used for this index
  query       queries the index
  registry    registry lists the bleve components compiled into this executable
  scorch      command-line tool to interact with a scorch index

Flags:
  -h, --help   help for bleve

Use "bleve [command] --help" for more information about a command.
```

## Text Analysis

Bleve includes general-purpose analyzers (customizable) as well as pre-built text analyzers for the following languages:

Arabic (ar), Bulgarian (bg), Catalan (ca), Chinese-Japanese-Korean (cjk), Kurdish (ckb), Danish (da), German (de), Greek (el), English (en), Spanish - Castilian (es), Basque (eu), Persian (fa), Finnish (fi), French (fr), Gaelic (ga), Spanish - Galician (gl), Hindi (hi), Croatian (hr), Hungarian (hu), Armenian (hy), Indonesian (id, in), Italian (it), Dutch (nl), Norwegian (no), Polish (pl), Portuguese (pt), Romanian (ro), Russian (ru), Swedish (sv), Turkish (tr)

## Text Analysis Wizard

[bleveanalysis.couchbase.com](https://bleveanalysis.couchbase.com)

## Discussion/Issues

Discuss usage/development of bleve and/or report issues here:

* [Github issues](https://github.com/blevesearch/bleve/issues)
* [Google group](https://groups.google.com/forum/#!forum/bleve)

## License

Apache License Version 2.0


bleve

An Adaptive Radix Tree Implementation in Go
====

[![Coverage Status](https://coveralls.io/repos/github/plar/go-adaptive-radix-tree/badge.svg?branch=master&v=1)](https://coveralls.io/github/plar/go-adaptive-radix-tree?branch=master) [![Go Report Card](https://goreportcard.com/badge/github.com/plar/go-adaptive-radix-tree)](https://goreportcard.com/report/github.com/plar/go-adaptive-radix-tree) [![GoDoc](https://godoc.org/github.com/plar/go-adaptive-radix-tree?status.svg)](https://pkg.go.dev/github.com/plar/go-adaptive-radix-tree/v2)

This library provides a Go implementation of the Adaptive Radix Tree (ART).

Features:
* Lookup performance surpasses highly tuned alternatives
* Support for highly efficient insertions and deletions
* Space efficient
* Performance is comparable to hash tables
* Maintains the data in sorted order, which enables additional operations like range scan and prefix lookup
	> Keys are sorted **lexicographically** based on their byte values.
* `O(k)` search/insert/delete operations, where `k` is the length of the key
* Minimum / Maximum value lookups
* Ordered iteration
* Prefix-based iteration
* Reverse iteration support
* Support for keys with null bytes, any byte array could be a key

# Usage

[The Go playground](https://go.dev/play/p/tBJa0d50eOp)

```go
package main

import (
	"fmt"
	art "github.com/plar/go-adaptive-radix-tree/v2"
)

func main() {
	// Initialize a new Adaptive Radix Tree
	tree := art.New()

	// Insert key-value pairs into the tree
	tree.Insert(art.Key("apple"), "A sweet red fruit")
	tree.Insert(art.Key("banana"), "A long yellow fruit")
	tree.Insert(art.Key("cherry"), "A small red fruit")
	tree.Insert(art.Key("date"), "A sweet brown fruit")

	// Search for a value by key
	if value, found := tree.Search(art.Key("banana")); found {
		fmt.Println("Found:", value)
	} else {
		fmt.Println("Key not found")
	}

	// Iterate over the tree in ascending order
	fmt.Println("\nAscending order iteration:")
	tree.ForEach(func(node art.Node) bool {
		fmt.Printf("Key: %s, Value: %s\n", node.Key(), node.Value())
		return true
	})

	// Iterate over the tree in descending order using reverse traversal
	fmt.Println("\nDescending order iteration:")
	tree.ForEach(func(node art.Node) bool {
		fmt.Printf("Key: %s, Value: %s\n", node.Key(), node.Value())
		return true
	}, art.TraverseReverse)

	// Iterate over keys with a specific prefix
	fmt.Println("\nIteration with prefix 'c':")
	tree.ForEachPrefix(art.Key("c"), func(node art.Node) bool {
		fmt.Printf("Key: %s, Value: %s\n", node.Key(), node.Value())
		return true
	})
}

// Expected Output:
// Found: A long yellow fruit
//
// Ascending order iteration:
// Key: apple, Value: A sweet red fruit
// Key: banana, Value: A long yellow fruit
// Key: cherry, Value: A small red fruit
// Key: date, Value: A sweet brown fruit
//
// Descending order iteration:
// Key: date, Value: A sweet brown fruit
// Key: cherry, Value: A small red fruit
// Key: banana, Value: A long yellow fruit
// Key: apple, Value: A sweet red fruit
//
// Iteration with prefix 'c':
// Key: cherry, Value: A small red fruit
```

# Documentation

Check out the documentation on [pkg.go.dev/github.com/plar/go-adaptive-radix-tree/v2](https://pkg.go.dev/github.com/plar/go-adaptive-radix-tree/v2).

# Migration from v1 to v2

- update `import` statement

``` 
from `art "github.com/plar/go-adaptive-radix-tree"`
  to `art "github.com/plar/go-adaptive-radix-tree/v2"`
```

- update go module dependency

```
$ go get github.com/plar/go-adaptive-radix-tree/v2
$ go mod tidy
```

If you had implemented your own version of the `Tree` interface, then you need to update the following method to support `options`. These are the only changes in the interface.

```
	ForEachPrefix(keyPrefix Key, callback Callback, options ...int)
```

# Performance

[plar/go-adaptive-radix-tree](https://github.com/plar/go-adaptive-radix-tree) outperforms [kellydunn/go-art](https://github.com/kellydunn/go-art) by avoiding memory allocations during search operations.
It also provides prefix based and reverse iteration over the tree.

Benchmarks were performed on datasets extracted from different projects:
- The "Words" dataset contains a list of 235,886 english words. [2]
- The "UUIDs" dataset contains 100,000 uuids.                   [2]
- The "HSK Words" dataset contains 4,995 words.                 [4]

|**go-adaptive-radix-tree**| #  | Average time      |Bytes per operation|Allocs per operation |
|:-------------------------|---:|------------------:|------------------:|--------------------:|
|       Tree Insert Words  |  9 | 117,888,698 ns/op |  37,942,744  B/op | 1,214,541 allocs/op |
|       Tree Search Words  | 26 |  44,555,608 ns/op |            0 B/op |         0 allocs/op |
|       Tree Insert UUIDs  | 18 |  59,360,135 ns/op |   18,375,723 B/op |   485,057 allocs/op |
|       Tree Search UUIDs  | 54 |  21,265,931 ns/op |            0 B/op |         0 allocs/op |
|**go-art**                |    |                   |                   |                     |
|       Tree Insert Words  |  5 | 272,047,975 ns/op |   81,628,987 B/op | 2,547,316 allocs/op |
|       Tree Search Words  | 10 | 129,011,177 ns/op |   13,272,278 B/op | 1,659,033 allocs/op |
|       Tree Insert UUIDs  | 10 | 140,309,246 ns/op |   33,678,160 B/op |   874,561 allocs/op |
|       Tree Search UUIDs  | 20 |  82,120,943 ns/op |    3,883,131 B/op |   485,391 allocs/op |

To see more benchmarks just run

```
$ ./make qa/benchmarks
```

# References

[1] [The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases (Specification)](http://www-db.in.tum.de/~leis/papers/ART.pdf)

[2] [C99 implementation of the Adaptive Radix Tree](https://github.com/armon/libart)

[3] [Another Adaptive Radix Tree implementation in Go](https://github.com/kellydunn/go-art)

[4] [HSK Words](http://hskhsk.pythonanywhere.com/hskwords). HSK(Hanyu Shuiping Kaoshi) - Standardized test of Standard Mandarin Chinese proficiency.


go-adaptive-radix-tree

Go string comparison and edit distance algorithms library (Levenshtein, LCS, Hamming, Damerau levenshtein, Jaro-Winkler, etc.) compatible with Unicode

<h1 align="center">Go-edlib : Edit distance and string comparison library</h1>

<p align="center">
  <a href='https://coveralls.io/github/hbollon/go-edlib?branch=master'>
    <img src='https://coveralls.io/repos/github/hbollon/go-edlib/badge.svg?branch=master' alt='Coverage Status' />
  </a>
  <a href="https://goreportcard.com/report/github.com/hbollon/go-edlib" target="_blank">
    <img alt="Go Report Card" src="https://goreportcard.com/badge/github.com/hbollon/go-edlib" />
  </a>
  <a href="https://github.com/hbollon/go-edlib/blob/master/LICENSE.md" target="_blank">
    <img alt="License: MIT" src="https://img.shields.io/badge/License-MIT-yellow.svg" />
  </a>
  <a href="https://pkg.go.dev/github.com/hbollon/go-edlib" target="_blank">
    <img src="https://pkg.go.dev/badge/github.com/hbollon/go-edlib" alt="PkgGoDev">
  </a>
</p>

> Golang string comparison and edit distance algorithms library featuring : Levenshtein, LCS, Hamming, Damerau levenshtein (OSA and Adjacent transpositions algorithms), Jaro-Winkler, Cosine, etc...

---

## Table of Contents

- [Requirements](#requirements)
- [Introduction](#introduction)
- [Features](#features)
- [Installation](#installation)
- [Benchmarks](#benchmarks)
- [Documentation](#documentation)
- [Examples](#examples)
- [Author](#author)
- [Contributing](#-contributing)
- [License](#-license)


---

## Requirements
- [Go](https://golang.org/doc/install) (v1.13+)

## Introduction
Golang open-source library which includes most (and soon all) edit-distance and string comparision algorithms with some extra! <br>
Designed to be fully compatible with Unicode characters!<br>
This library is 100% test covered 😁

## Features

- [Levenshtein](https://en.wikipedia.org/wiki/Levenshtein_distance)
- [LCS](https://en.wikipedia.org/wiki/Longest_common_subsequence_problem) (Longest common subsequence) with edit distance, backtrack and diff functions
- [Hamming](https://en.wikipedia.org/wiki/Hamming_distance)
- [Damerau-Levenshtein](https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance), with following variants:
  - OSA (Optimal string alignment)
  - Adjacent transpositions
- [Jaro & Jaro-Winkler](https://en.wikipedia.org/wiki/Jaro%E2%80%93Winkler_distance) similarity algorithms
- [Cosine Similarity](https://en.wikipedia.org/wiki/Cosine_similarity)
- [Jaccard Index](https://en.wikipedia.org/wiki/Jaccard_index)
- [QGram](https://en.wikipedia.org/wiki/N-gram)
- [Sorensen-Dice](https://en.wikipedia.org/wiki/S%C3%B8rensen%E2%80%93Dice_coefficient)
- Computed similarity percentage functions based on all available edit distance algorithms in this lib
- Fuzzy search functions based on edit distance with unique or multiples strings output
- Unicode compatibility 🥳

## Benchmarks
You can check an interactive Google chart with few benchmark cases for all similarity algorithms in this library through **StringsSimilarity** function [here](http://benchgraph.codingberg.com/q5)

However, if you want or need more details, you can also viewing benchmark raw output [here](https://github.com/hbollon/go-edlib/blob/master/tests/outputs/benchmarks.txt), which also includes memory allocations and test cases output (similarity result and errors).

If you are on Linux and want to run them on your setup, you can run ``` ./tests/benchmark.sh ``` script.

## Installation
Open bash into your project folder and run:

```bash
go get github.com/hbollon/go-edlib
```

And import it into your project:

```go
import (
	"github.com/hbollon/go-edlib"
)
```

### Run tests
If you are on Linux and want to run all unit tests just run ``` ./tests/tests.sh ``` script. 

For Windows users you can run:

```bash
go test ./... # Add desired parameters to this command if you want
```

## Documentation

**You can find all the documentation here :** [Documentation](https://godoc.org/github.com/hbollon/go-edlib) 

## Examples

### Calculate string similarity index between two string

You can use ``` StringSimilarity(str1, str2, algorithm) ``` function.
**algorithm** parameter must one of the following constants: 
```go
// Algorithm identifiers
const (
	Levenshtein Algorithm = iota
	DamerauLevenshtein
	OSADamerauLevenshtein
	Lcs
	Hamming
	Jaro
	JaroWinkler
	Cosine
)
```

Example with levenshtein:
```go
res, err := edlib.StringsSimilarity("string1", "string2", edlib.Levenshtein)
if err != nil {
  fmt.Println(err)
} else {
  fmt.Printf("Similarity: %f", res)
}
```

### Execute fuzzy search based on string similarity algorithm

#### 1. Most matching unique result without threshold

You can use ``` FuzzySearch(str, strList, algorithm) ``` function.

```go
strList := []string{"test", "tester", "tests", "testers", "testing", "tsting", "sting"}
res, err := edlib.FuzzySearch("testnig", strList, edlib.Levenshtein)
if err != nil {
  fmt.Println(err)
} else {
  fmt.Printf("Result: %s", res)
}

```

``` 
Result: testing 
```

#### 2. Most matching unique result with threshold

You can use ``` FuzzySearchThreshold(str, strList, minSimilarity, algorithm) ``` function.

```go
strList := []string{"test", "tester", "tests", "testers", "testing", "tsting", "sting"}
res, err := edlib.FuzzySearchThreshold("testnig", strList, 0.7, edlib.Levenshtein)
if err != nil {
  fmt.Println(err)
} else {
  fmt.Printf("Result for 'testnig': %s", res)
}

res, err = edlib.FuzzySearchThreshold("hello", strList, 0.7, edlib.Levenshtein)
if err != nil {
  fmt.Println(err)
} else {
  fmt.Printf("Result for 'hello': %s", res)
}

```

``` 
Result for 'testnig': testing
Result for 'hello':
```

#### 3. Most matching result set without threshold

You can use ``` FuzzySearchSet(str, strList, resultQuantity, algorithm) ``` function.

```go
strList := []string{"test", "tester", "tests", "testers", "testing", "tsting", "sting"}
res, err := edlib.FuzzySearchSet("testnig", strList, 3, edlib.Levenshtein)
if err != nil {
  fmt.Println(err)
} else {
  fmt.Printf("Results: %s", strings.Join(res, ", "))
}

```

``` 
Results: testing, test, tester 
```

#### 4. Most matching result set with threshold

You can use ``` FuzzySearchSetThreshold(str, strList, resultQuantity, minSimilarity, algorithm) ``` function.

```go
strList := []string{"test", "tester", "tests", "testers", "testing", "tsting", "sting"}
res, err := edlib.FuzzySearchSetThreshold("testnig", strList, 3, 0.5, edlib.Levenshtein)
if err != nil {
  fmt.Println(err)
} else {
  fmt.Printf("Result for 'testnig' with '0.5' threshold: %s", strings.Join(res, " "))
}

res, err = edlib.FuzzySearchSetThreshold("testnig", strList, 3, 0.7, edlib.Levenshtein)
if err != nil {
  fmt.Println(err)
} else {
  fmt.Printf("Result for 'testnig' with '0.7' threshold: %s", strings.Join(res, " "))
}

```

``` 
Result for 'testnig' with '0.5' threshold: testing test tester
Result for 'testnig' with '0.7' threshold: testing
```

### Get raw edit distance (Levenshtein, LCS, Damerau–Levenshtein, Hamming)

You can use one of the following function to get an edit distance between two strings :
- [LevenshteinDistance](https://pkg.go.dev/github.com/hbollon/go-edlib#LevenshteinDistance)(str1, str2)
- [DamerauLevenshteinDistance](https://pkg.go.dev/github.com/hbollon/go-edlib#DamerauLevenshteinDistance)(str1, str2)
- [OSADamerauLevenshteinDistance](https://pkg.go.dev/github.com/hbollon/go-edlib#OSADamerauLevenshteinDistance)(str1, str2)
- [LCSEditDistance](https://pkg.go.dev/github.com/hbollon/go-edlib#LCSEditDistance)(str1, str2)
- [HammingDistance](https://pkg.go.dev/github.com/hbollon/go-edlib#HammingDistance)(str1, str2)

Example with Levenshtein distance:
```go
res := edlib.LevenshteinDistance("kitten", "sitting")
fmt.Printf("Result: %d", res)
```

```
Result: 3
```

### LCS, LCS Backtrack and LCS Diff
#### 1. Compute LCS(Longuest Common Subsequence) between two strings

You can use ``` LCS(str1, str2) ``` function.

```go
lcs := edlib.LCS("ABCD", "ACBAD")
fmt.Printf("Length of their LCS: %d", lcs)
```

```
Length of their LCS: 3
```

#### 2. Backtrack their LCS

You can use ``` LCSBacktrack(str1, str2) ``` function.

```go
res, err := edlib.LCSBacktrack("ABCD", "ACBAD")
if err != nil {
  fmt.Println(err)
} else {
  fmt.Printf("LCS: %s", res)
}
```

```
LCS: ABD
```

#### 3. Backtrack all their LCS

You can use ``` LCSBacktrackAll(str1, str2) ``` function.

```go
res, err := edlib.LCSBacktrackAll("ABCD", "ACBAD")
if err != nil {
  fmt.Println(err)
} else {
  fmt.Printf("LCS: %s", strings.Join(res, ", "))
}
```

```
LCS: ABD, ACD
```

#### 4. Get LCS Diff between two strings

You can use ``` LCSDiff(str1, str2) ``` function.

```go
res, err := edlib.LCSDiff("computer", "houseboat")
if err != nil {
  fmt.Println(err)
} else {
  fmt.Printf("LCS: \n%s\n%s", res[0], res[1])
}
```

```
LCS Diff: 
 h c o m p u s e b o a t e r
 + -   - -   + + + + +   - -
```

## Author

👤 **Hugo Bollon**

* Github: [@hbollon](https://github.com/hbollon)
* LinkedIn: [@Hugo Bollon](https://www.linkedin.com/in/hugo-bollon-68a2381a4/)
* Portfolio: [hugobollon.me](https://www.hugobollon.me)

## 🤝 Contributing

Contributions, issues and feature requests are welcome!<br />Feel free to check [issues page](https://github.com/hbollon/go-edlib/issues). 

## Show your support

Give a ⭐️ if this project helped you!

## 📝 License

Copyright © 2020 [Hugo Bollon](https://github.com/hbollon).<br />
This project is [MIT License](https://github.com/hbollon/go-edlib/blob/master/LICENSE.md) licensed.


go-edlib

Levenshtein distance and similarity metrics with customizable edit costs and Winkler-like bonus for common prefix

# A Go package for calculating the Levenshtein distance between two strings

[![Release](https://img.shields.io/github/release/agext/levenshtein.svg?style=flat)](https://github.com/agext/levenshtein/releases/latest)
[![GoDoc](https://img.shields.io/badge/godoc-reference-blue.svg?style=flat)](https://godoc.org/github.com/agext/levenshtein) 
[![Build Status](https://travis-ci.org/agext/levenshtein.svg?branch=master&style=flat)](https://travis-ci.org/agext/levenshtein)
[![Coverage Status](https://coveralls.io/repos/github/agext/levenshtein/badge.svg?style=flat)](https://coveralls.io/github/agext/levenshtein)
[![Go Report Card](https://goreportcard.com/badge/github.com/agext/levenshtein?style=flat)](https://goreportcard.com/report/github.com/agext/levenshtein)


This package implements distance and similarity metrics for strings, based on the Levenshtein measure, in [Go](http://golang.org).

## Project Status

v1.2.3 Stable: Guaranteed no breaking changes to the API in future v1.x releases. Probably safe to use in production, though provided on "AS IS" basis.

This package is being actively maintained. If you encounter any problems or have any suggestions for improvement, please [open an issue](https://github.com/agext/levenshtein/issues). Pull requests are welcome.

## Overview

The Levenshtein `Distance` between two strings is the minimum total cost of edits that would convert the first string into the second. The allowed edit operations are insertions, deletions, and substitutions, all at character (one UTF-8 code point) level. Each operation has a default cost of 1, but each can be assigned its own cost equal to or greater than 0.

A `Distance` of 0 means the two strings are identical, and the higher the value the more different the strings. Since in practice we are interested in finding if the two strings are "close enough", it often does not make sense to continue the calculation once the result is mathematically guaranteed to exceed a desired threshold. Providing this value to the `Distance` function allows it to take a shortcut and return a lower bound instead of an exact cost when the threshold is exceeded.

The `Similarity` function calculates the distance, then converts it into a normalized metric within the range 0..1, with 1 meaning the strings are identical, and 0 that they have nothing in common. A minimum similarity threshold can be provided to speed up the calculation of the metric for strings that are far too dissimilar for the purpose at hand. All values under this threshold are rounded down to 0.

The `Match` function provides a similarity metric, with the same range and meaning as `Similarity`, but with a bonus for string pairs that share a common prefix and have a similarity above a "bonus threshold". It uses the same method as proposed by Winkler for the Jaro distance, and the reasoning behind it is that these string pairs are very likely spelling variations or errors, and they are more closely linked than the edit distance alone would suggest.

The underlying `Calculate` function is also exported, to allow the building of other derivative metrics, if needed.

## Installation

```
go get github.com/agext/levenshtein
```

## License

Package levenshtein is released under the Apache 2.0 license. See the [LICENSE](LICENSE) file for details.


levenshtein

Implementation to calculate levenshtein distance in Go

levenshtein ![Build Status](https://github.com/agnivade/levenshtein/actions/workflows/ci.yml/badge.svg) [![Go Report Card](https://goreportcard.com/badge/github.com/agnivade/levenshtein)](https://goreportcard.com/report/github.com/agnivade/levenshtein) [![PkgGoDev](https://pkg.go.dev/badge/github.com/agnivade/levenshtein)](https://pkg.go.dev/github.com/agnivade/levenshtein)
===========

[Go](http://golang.org) package to calculate the [Levenshtein Distance](http://en.wikipedia.org/wiki/Levenshtein_distance)

The library is fully capable of working with non-ascii strings. But the strings are not normalized. That is left as a user-dependant use case. Please normalize the strings before passing it to the library if you have such a requirement.
- https://blog.golang.org/normalization

#### Limitation

As a performance optimization, the library can handle strings only up to 65536 characters (runes). If you need to handle strings larger than that, please pin to version 1.0.3.

Install
-------

    go get github.com/agnivade/levenshtein

Example
-------

```go
package main

import (
	"fmt"
	"github.com/agnivade/levenshtein"
)

func main() {
	s1 := "kitten"
	s2 := "sitting"
	distance := levenshtein.ComputeDistance(s1, s2)
	fmt.Printf("The distance between %s and %s is %d.\n", s1, s2, distance)
	// Output:
	// The distance between kitten and sitting is 3.
}

```

Benchmarks
----------

```
goos: darwin
goarch: arm64
pkg: github.com/agnivade/levenshtein
cpu: Apple M4
                      │  bench.out  │
                      │   sec/op    │
Simple/ASCII-10         123.8n ± 0%
Simple/French-10        212.6n ± 1%
Simple/Nordic-10        365.9n ± 0%
Simple/Long_lead-10     224.5n ± 0%
Simple/Long_middle-10   379.9n ± 0%
Simple/Long_trail-10    580.8n ± 0%
Simple/Long_diff-10     8.008µ ± 0%
Simple/Tibetan-10       459.5n ± 0%
geomean                 452.4n

                      │  bench.out   │
                      │     B/op     │
Simple/ASCII-10         0.000 ± 0%
Simple/French-10        0.000 ± 0%
Simple/Nordic-10        0.000 ± 0%
Simple/Long_lead-10     368.0 ± 0%
Simple/Long_middle-10   544.0 ± 0%
Simple/Long_trail-10    576.0 ± 0%
Simple/Long_diff-10     720.0 ± 0%
Simple/Tibetan-10       0.000 ± 0%
geomean                            ¹
¹ summaries must be >0 to compute geomean

                      │  bench.out   │
                      │  allocs/op   │
Simple/ASCII-10         0.000 ± 0%
Simple/French-10        0.000 ± 0%
Simple/Nordic-10        0.000 ± 0%
Simple/Long_lead-10     2.000 ± 0%
Simple/Long_middle-10   2.000 ± 0%
Simple/Long_trail-10    2.000 ± 0%
Simple/Long_diff-10     3.000 ± 0%
Simple/Tibetan-10       0.000 ± 0%
geomean                            ¹
¹ summaries must be >0 to compute geomean
```

Comparisons with other libraries
--------------------------------

### github.com/dgryski/trifles

```
goos: darwin
goarch: arm64
pkg: github.com/agnivade/levenshtein
cpu: Apple M4
                    │   dgryski   │               agniva                │
                    │   sec/op    │   sec/op     vs base                │
All/case=ASCII-10     288.4n ± 0%   123.9n ± 1%  -57.05% (p=0.000 n=20)
All/case=French-10    518.8n ± 0%   211.7n ± 1%  -59.20% (p=0.000 n=20)
All/case=Nordic-10    963.8n ± 0%   369.4n ± 1%  -61.67% (p=0.000 n=20)
All/case=Tibetan-10   795.6n ± 0%   460.1n ± 0%  -42.18% (p=0.000 n=20)
geomean               582.0n        258.4n       -55.60%

                    │  dgryski   │                 agniva                 │
                    │    B/op    │   B/op     vs base                     │
All/case=ASCII-10     96.00 ± 0%   0.00 ± 0%  -100.00% (p=0.000 n=20)
All/case=French-10    128.0 ± 0%    0.0 ± 0%  -100.00% (p=0.000 n=20)
All/case=Nordic-10    192.0 ± 0%    0.0 ± 0%  -100.00% (p=0.000 n=20)
All/case=Tibetan-10   160.0 ± 0%    0.0 ± 0%  -100.00% (p=0.000 n=20)
geomean               139.4                   ?                       ¹ ²
¹ summaries must be >0 to compute geomean
² ratios must be >0 to compute geomean

                    │  dgryski   │                 agniva                  │
                    │ allocs/op  │ allocs/op   vs base                     │
All/case=ASCII-10     1.000 ± 0%   0.000 ± 0%  -100.00% (p=0.000 n=20)
All/case=French-10    1.000 ± 0%   0.000 ± 0%  -100.00% (p=0.000 n=20)
All/case=Nordic-10    1.000 ± 0%   0.000 ± 0%  -100.00% (p=0.000 n=20)
All/case=Tibetan-10   1.000 ± 0%   0.000 ± 0%  -100.00% (p=0.000 n=20)
geomean               1.000                    ?                       ¹ ²
¹ summaries must be >0 to compute geomean
² ratios must be >0 to compute geomean
```

### github.com/arbovm/levenshtein

```
goos: darwin
goarch: arm64
pkg: github.com/agnivade/levenshtein
cpu: Apple M4
                    │   arbovm    │               agniva                │
                    │   sec/op    │   sec/op     vs base                │
All/case=ASCII-10     283.1n ± 1%   123.9n ± 1%  -56.23% (p=0.000 n=20)
All/case=French-10    516.4n ± 0%   211.7n ± 1%  -59.01% (p=0.000 n=20)
All/case=Nordic-10    978.9n ± 0%   369.4n ± 1%  -62.26% (p=0.000 n=20)
All/case=Tibetan-10   804.9n ± 0%   460.1n ± 0%  -42.84% (p=0.000 n=20)
geomean               582.6n        258.4n       -55.65%

                    │   arbovm   │                 agniva                 │
                    │    B/op    │   B/op     vs base                     │
All/case=ASCII-10     96.00 ± 0%   0.00 ± 0%  -100.00% (p=0.000 n=20)
All/case=French-10    128.0 ± 0%    0.0 ± 0%  -100.00% (p=0.000 n=20)
All/case=Nordic-10    192.0 ± 0%    0.0 ± 0%  -100.00% (p=0.000 n=20)
All/case=Tibetan-10   160.0 ± 0%    0.0 ± 0%  -100.00% (p=0.000 n=20)
geomean               139.4                   ?                       ¹ ²
¹ summaries must be >0 to compute geomean
² ratios must be >0 to compute geomean

                    │   arbovm   │                 agniva                  │
                    │ allocs/op  │ allocs/op   vs base                     │
All/case=ASCII-10     1.000 ± 0%   0.000 ± 0%  -100.00% (p=0.000 n=20)
All/case=French-10    1.000 ± 0%   0.000 ± 0%  -100.00% (p=0.000 n=20)
All/case=Nordic-10    1.000 ± 0%   0.000 ± 0%  -100.00% (p=0.000 n=20)
All/case=Tibetan-10   1.000 ± 0%   0.000 ± 0%  -100.00% (p=0.000 n=20)
geomean               1.000                    ?                       ¹ ²
¹ summaries must be >0 to compute geomean
² ratios must be >0 to compute geomean
```

# Trie (Prefix tree)

[![GoReportCard](https://goreportcard.com/badge/github.com/viant/ptrie)](https://goreportcard.com/report/github.com/viant/ptrie)
[![GoDoc](https://godoc.org/github.com/viant/ptrie?status.svg)](https://godoc.org/github.com/viant/ptrie)


This library is compatible with Go 1.11+

Please refer to [`CHANGELOG.md`](CHANGELOG.md) if you encounter breaking changes.

- [Motivation](#motivation)
- [Introduction](#introduction)
- [Usage](#usage)
- [Benchmark](#benchmark)

## Motivation

The goal of this project is to provide serverless prefix tree friendly implementation.
 where one function can easily building tree and publishing to some cloud storge.
Then the second load trie to perform various operations.

## Introduction


A  trie (prefix tree) is a space-optimized tree data structure  in which each node that is merged with its parent.
Unlike regular trees (where whole keys are from their beginning up to the point of inequality), the key at each node is compared chunk by chunk,


Prefix tree has the following application:

 - text document searching
 - rule based matching
 - constructing associative arrays for string keys

 
Character comparision complexity:

* **Brute Force:** _O(d n k)_
* **Prefix Trie**: _O(d log(k))_

Where
- d: number of characters in document
- n: number of keywords
- k: average keyword length


### Usage


```go

    trie := ptrie.New()
    for key, value := range pairs {
        if err = trie.Put(key, value); err != nil {
            log.Fatal(err)
         }
    }
    //...
    has := trie.Has(key)
    value, has := trie.Get(key)
    //...
    matched := trie.MatchAll(input,  func(key []byte, value interface{}) bool {
        fmt.Printf("matched: key: %s, value %v\n", key, value)
        return true 
    })
    
```

1. Building


```go

    trie := ptrie.New()
    
    for key, value := range pairs {
         if err = trie.Put(key, value); err != nil {
         	log.Fatal(err)
         }
    }
    
    writer := new(bytes.Buffer)
	if err := trie.Encode(writer); err != nil {
		log.Fatal(err)
	}
	encoded := write.Bytes()
	//write encode data

```

2. Loading

```go

    //V type can be any type
    var v *V
    

    trie := ptrie.New()
    trie.UseType(reflect.TypeOf(v))
    if err := trie.Decode(reader); err != nil {
    	log.Fatal(err)
    }

```    

3. Traversing (range map)

```go

    trie.Walk(func(key []byte, value interface{}) bool {
		fmt.Printf("key: %s, value %v\n", key, value)
		return true
	})

```

4. Lookup

```go

    has := trie.Has(key)
    value, has := trie.Get(key)

```

5. MatchPrefix

```go

    var input []byte
    ...

    matched := trie.MatchPrefix(input,  func(key []byte, value interface{}) bool {
        fmt.Printf("matched: key: %s, value %v\n", key, value)
        return true 
    })

```

6. MatchAll

```go

    var input []byte
    ...

    matched := trie.MatchAll(input,  func(key []byte, value interface{}) bool {
        fmt.Printf("matched: key: %s, value %v\n", key, value)
        return true 
    })

```

#### Benchmark

The benchmark count all words that are part of the following extracts:

**[Lorem Ipsum](test/lorem.txt)**

1. Short: avg line size: 20, words: 13
2. Long: avg line size: 711, words: 551


```bash
Benchmark_LoremBruteForceShort-8    	  500000	      3646 ns/op
Benchmark_LoremTrieShort-8          	  500000	      2376 ns/op
Benchmark_LoremBruteForceLong-8     	    1000	   1612877 ns/op
Benchmark_LoremTrieLong-8           	   10000	    119990 ns/op
```

**[Hamlet](test/hamlet.txt)**

1. Short: avg line size: 20, words: 49
2. Long: avg line size: 41, words: 105

```bash
Benchmark_HamletBruteForceShort-8   	   30000	     44306 ns/op
Benchmark_HamletTrieShort-8         	  100000	     18530 ns/op
Benchmark_HamletBruteForceLong-8    	   10000	    226836 ns/op
Benchmark_HamletTrieLong-8          	   50000	     39329 ns/op
```

##### Code coverage

[![GoCover](https://gocover.io/github.com/viant/ptrie)](https://gocover.io/github.com/viant/ptrie)


<a name="License"></a>
## License

The source code is made available under the terms of the Apache License, Version 2, as stated in the file `LICENSE`.

Individual files may be made available under their own specific license,
all compatible with Apache License, Version 2. Please see individual files for details.


<a name="Credits-and-Acknowledgements"></a>

##  Credits and Acknowledgements

**Library Author:** Adrian Witas


ptrie

Tools for parse JSON-like logs for collecting unique fields and events

[![Codacy Badge](https://api.codacy.com/project/badge/Grade/dc9f7432a97a4d5296045487e1db44f1)](https://app.codacy.com/app/MonaxGT/parsefields?utm_source=github.com&utm_medium=referral&utm_content=MonaxGT/parsefields&utm_campaign=Badge_Grade_Dashboard)
[![GoDoc](https://godoc.org/github.com/MonaxGT/parsefields?status.png)](https://godoc.org/github.com/MonaxGT/parsefields)
[![Build Status](https://travis-ci.com/MonaxGT/gomalshare.svg?branch=master)](https://travis-ci.com/MonaxGT/gomalshare)
[![Go Report Card](https://goreportcard.com/badge/github.com/MonaxGT/parsefields)](https://goreportcard.com/report/github.com/MonaxGT/parsefields)
[![Say Thanks!](https://img.shields.io/badge/Say%20Thanks-!-1EAEDB.svg)](https://saythanks.io/to/MonaxGT)

# parsefields

Tool for parse JSON-like logs for collecting unique fields. Main purpose to collect JSON-data with typical events and fields it is useful when you want to create mapping schema for database and you want to reduce the risks of forgotten fields. 
By default separator between to nested structs is "->", but you can change it with environment.

API consist:

```
-  POST /v1/json/
-  POST /v1/mjson/
-  GET /v1/fileds/
-  GET  /v1/events/
-  GET /v1/events/:logname/:eventid
-  DELETE /v1/events/:logname/:eventid
-  DELETE /v1/fields/:field
```

P.S. additionally info about all new events/fields will be show in stdout.

## Deploy

```sh
docker build . -t parsefield
docker run -d -p 8000:8000 parsefield
```

or 

```sh
docker-compose -p 8000:8000 -d up 
```

## Usage

### Push new log for parse

Single message per request

```sh
curl -X POST -d '{"process_name": "calc.exe", "process_path":"C:\\windows\\system32"}'  127.0.0.1:8000/v1/json/
```

Multiple message per request 

```sh
curl -X POST -d '[{"process_name": "calc.exe", "process_path":"C:\\windows\\system32"},{"process_image": "calc.exe", "process_path":"C:\\windows\\system32"},{"pid":"1"}]'  127.0.0.1:8000/v1/mjson/
```

### All unique fields

```sh
curl 127.0.0.1:8000/v1/fields/
```

### All unique events

```sh
curl 127.0.0.1:8000/v1/events/
```

### Show body of event

```sh
curl 127.0.0.1:8000/v1/events/Sysmon/999 
```

### Delete events, fields

```sh
curl -X DELETE 127.0.0.1:8000/v1/events/Sysmon/999 - delete events with logname Sysmon and eventId 999
curl -X DELETE 127.0.0.1:8000/v1/fields/key - delete field with name key
```


parsefields

[![GoDoc](https://godoc.org/github.com/derekparker/trie?status.svg)](https://godoc.org/github.com/derekparker/trie)

# Trie
Data structure and relevant algorithms for extremely fast prefix/fuzzy string searching.

## Usage

Create a Trie with:

```Go
t := trie.New()
```

Add Keys with:

```Go
// Add can take in meta information which can be stored with the key.
// i.e. you could store any information you would like to associate with
// this particular key.
t.Add("foobar", 1)
```

Find a key with:

```Go
node, ok := t.Find("foobar")
meta := node.Meta()
// use meta with meta.(type)
```

Remove Keys with:

```Go
t.Remove("foobar")
```

Prefix search with:

```Go
t.PrefixSearch("foo")
```

Fast test for valid prefix:
```Go
t.HasKeysWithPrefix("foo")
```

Fuzzy search with:

```Go
t.FuzzySearch("fb")
```

## Contributing
Fork this repo and run tests with:

	go test

Create a feature branch, write your tests and code and submit a pull request.

## License
MIT


trie

Multi-String Pattern Matching Algorithm for information retrieval

# Multi-String Pattern Matching algorithm.
[![Go Report Card](https://goreportcard.com/badge/github.com/BlackRabbitt/mspm)](https://goreportcard.com/report/github.com/BlackRabbitt/mspm)
[![GoDoc](https://godoc.org/github.com/BlackRabbitt/mspm?status.svg)](https://godoc.org/github.com/BlackRabbitt/mspm)

This implementation is inspired from [Aho-Corasick algorithm](https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm)

## Getting Started
```
modelA = mspm.NewModel("mspm_model_A")
patternsToSearch = strings.NewReader(words) // words is newline seperated list of words/keywords

// build mspm model with patterns
modelA.Build(patternsToSearch)

inputString := "input document where the above pattern is searched for."
document := strings.NewReader(inputString)
output, err := modelA.MultiTermMatch(document)

// output ~= [{matched_word: n_count}, ..]
```

## Test Coverage
* [trie package](https://gocover.io/github.com/blackrabbitt/mspm/ds/trie)
* [mspm package](https://gocover.io/github.com/blackrabbitt/mspm/search)

## TrieNode vs TrieHashNode benchmark
```
$ cd github.com/BlackRabbitt/mspm/ds/trie
$ go test -bench=.
goos: darwin
goarch: amd64
pkg: github.com/BlackRabbitt/mspm/ds/trie
BenchmarkTrieNodeInsert-4             500000          2582 ns/op
BenchmarkTrieNodeSearch-4           10000000           205 ns/op
BenchmarkTrieHashNodeInsert-4        1000000          1491 ns/op
BenchmarkTrieHashNodeSearch-4       10000000           206 ns/op
PASS
ok      github.com/BlackRabbitt/mspm/ds/trie	8.795s
```

## Resources
1. [Trie](https://en.wikipedia.org/wiki/Trie)
2. [mspm](http://www.ijsrp.org/research_paper_jul2012/ijsrp-july-2012-101.pdf) - Multi-String Pattern Matching algorithm. Generally used for Information Retrieval.
3. [Aho-Corasick algorithm](https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm)


The Best Go Libraries For Data Structures and Algorithms - Text Analysis (9)

bleve

go-adaptive-radix-tree

go-edlib

levenshtein

levenshtein

ptrie

parsefields

trie

mspm