This is a simple auto-completion engine/server that is fast and efficient. It uses Ternary Search Tree (TST) as its main underlying data-structure which is storage efficient and allows for fast lookup.
go get github.com/zeyadyasser/autocom
Simple Example
import (
"fmt"
"github.com/zeyadyasser/autocom/engine/skip"
)
func main() {
opts := skip.Options{
MaxLevels: 5,
ToLower: true,
SkipBegin: true,
}
E := skip.NewSkipEngine(opts, nil) // nil to use default backend (TST)
E.Set("Mad Max: Fury Road", "value (any interface)")
E.Set("Furious 7", nil)
top, _ := E.TopN("Fu", 2)
for K, V := range top {
fmt.Printf("%v --> %v\n", K, V)
}
// Mad Max: Fury Road --> value (any interface)
// Furious 7 --> nil
top, _ = E.TopN("road", 2)
for K, V := range top {
fmt.Printf("%v --> %v\n", K, V)
}
// Mad Max: Fury Road --> value (any interface)
E.Remove("Mad Max: Fury Road")
top, _ = E.TopN("Fu", 2)
for K, V := range top {
fmt.Printf("%v --> %v\n", K, V)
}
// Furious 7 --> nil
}
Checkout the interactive movies search sample
Here the search is case-sensitive but exact prefix matches are required.
opts := skip.Options{}
Case-sensitive Example :
opts := skip.Options{}
E := skip.NewSkipEngine(opts, nil) // nil to use default backend (TST)
E.Set("Mad Max: Fury Road", nil)
E.Set("Furious 7", nil)
top, _ := E.TopN("mad", 2)
for K, V := range top {
fmt.Printf("%v --> %v\n", K, V)
}
// No results
top, _ = E.TopN("Mad", 2)
for K, V := range top {
fmt.Printf("%v --> %v\n", K, V)
}
// Mad Max: Fury Road --> nil
Exact Prefix Example :
opts := skip.Options{}
E := skip.NewSkipEngine(opts, nil) // nil to use default backend (TST)
E.Set("Mad Max: Fury Road", nil)
E.Set("Furious 7", nil)
top, _ := E.TopN("Fury", 2)
for K, V := range top {
fmt.Printf("%v --> %v\n", K, V)
}
// No results, because "Fury is not the exact prefix of any key"
top, _ = E.TopN("Fur", 2)
for K, V := range top {
fmt.Printf("%v --> %v\n", K, V)
}
// Furious 7 --> nil
Here the search is case insensitive but exact prefix matches are required.
opts := skip.Options{
ToLower: true,
}
Case-insensitive Example :
opts := skip.Options{
ToLower: true,
}
E := skip.NewSkipEngine(opts, nil) // nil to use default backend (TST)
E.Set("Mad Max: Fury Road", nil)
E.Set("Furious 7", nil)
top, _ := E.TopN("mad", 2)
for K, V := range top {
fmt.Printf("%v --> %v\n", K, V)
}
// Mad Max: Fury Road --> nil
Here the search is case-insensitive and matches keys where any of the first N(MaxLevels) words of the key matches the query.
opts := skip.Options{
MaxLevels: 5, // Here N is 5
ToLower: true, // Case-insensitive
SkipBegin: true,// Match by skipping up to the first N words
}
Skip Begin Example :
opts := skip.Options{
MaxLevels: 3, // Here N is 3
ToLower: true, // Case-insensitive
SkipBegin: true,// Match by skipping up to the first N words
}
E := skip.NewSkipEngine(opts, nil) // nil to use default backend (TST)
E.Set("Mad Max: Fury Road", nil)
// The following keys are stored.
// "mad max: fury road"
// "max: fury road"
// "fury road"
// "road" is not stored, because N = 3 and this is the 4th word.
E.Set("Furious 7", nil)
// The following keys are stored.
// "furious 7"
// "7"
top, _ := E.TopN("fu", 2)
for K, V := range top {
fmt.Printf("%v --> %v\n", K, V)
}
// Mad Max: Fury Road --> nil (Here Fury is matched)
// Furious 7 --> nil (Here Furious is matched)
The Engine interface offers three main methods.
Set(string, interface{}) error
example:
E := skip.NewSkipEngine(opts, nil)
err := E.Set("Key", "any interface")
Remove(string) error
example:
E := skip.NewSkipEngine(opts, nil)
err := E.Remove("Key")
Maps Top N autocomplete matching keys to their values.
TopN(string, int) (complete.Map, error)
where complete.Map
is map[string]interface{}
example:
E := skip.NewSkipEngine(opts, nil)
result, err := E.TopN("Key", 5)
// returns top 5 matching keys
- Clone the repo & cd to root of repository.
git clone https://github.com/zeyadyasser/autocom.git cd autocom
- Create a new .env file using the .env.dist as a template
- Fill in the missing secrets suitable for your environment
- Never check in the .env file, it is already included in .gitignore, and never add actual secrets in .env.dist
- (Optional) To run on your local machine, run the following command
go run .
- (Optional) To use Docker, run the following command
docker build -t autocom . docker run --env-file=.env --rm -p 9696:9696 autocom
- (Optional) To use docker-compose, run the following command
docker-compose build docker-compose up
POST /set You should send data in JSON format. Example:
curl --header "Content-Type: application/json" \
-X POST \
--data '{"key":"xyz","value":"xyz"}' \
http://user:password@localhost:9696/set
DELETE /remove You should send the key as a query parameter. Example:
curl -X DELETE http://user:password@localhost:9696/remove?key=xyz
GET /topn
You should send the key & number of results as query parameters.
If cnt
is not a number 400 Bad Request
is returned.
Returns a JSON map from keys to values.
Example:
curl -X GET http://user:password@localhost:9696/topn?key=xyz&cnt=5
This was tested with Intel Core I5 8400 with 8GB of 2400hz DDR4 RAM.
Disclaimer : This not an exhaustive benchmark by any means.
cd path/to/autocom/engine/skip
go test -bench=.
goos: windows
goarch: amd64
pkg: github.com/zeyadyasser/autocom/engine/skip
BenchmarkTSTSet1ShortKey-6 1000000 1121 ns/op 620 B/op 15 allocs/op
BenchmarkTSTSet1LongKey-6 2000000 1086 ns/op 618 B/op 15 allocs/op
BenchmarkTSTTopN10ShortKey-6 1000000 1835 ns/op 1420 B/op 14 allocs/op
PASS
ok github.com/zeyadyasser/autocom/engine/skip 6.629s
- Add Tests