A comprehensive, Lodash-like utility library for Go

lancet

# Your basic radix sort [![GoDoc](https://godoc.org/github.com/yourbasic/radix?status.svg)][godoc-radix]

### A fast string sorting algorithm

This is an optimized sorting algorithm equivalent to `sort.Strings`
in the Go standard library. For string sorting, a carefully implemented
radix sort can be considerably faster than Quicksort, sometimes
**more than twice as fast**.

### MSD radix sort

![Radix sort](res/radix.png)

A discussion of **MSD radix sort**, its implementation and a comparison
with other well-known sorting algorithms can be found in
[Implementing radixsort][implradix]. In summary, MSD radix sort
uses O(n) extra space and runs in O(n+B) worst-case time,
where n is the number of strings to be sorted and B
is the number of bytes that must be inspected to sort the strings.

### Installation

Once you have [installed Go][golang-install], run the `go get` command
to install the `radix` package:

    go get github.com/yourbasic/radix


### Documentation

There is an online reference for the package at
[godoc.org/github.com/yourbasic/radix][godoc-radix].


### Roadmap

* The API of this library is frozen.
* Version numbers adhere to [semantic versioning][sv].

Stefan Nilsson – [korthaj](https://github.com/korthaj)

[godoc-radix]: https://godoc.org/github.com/yourbasic/radix
[golang-install]: http://golang.org/doc/install.html
[implradix]: https://www.nada.kth.se/~snilsson/publications/Radixsort-implementation/
[sv]: http://semver.org/


radix

Alternative suggestions with respect to keyboard layouts

# TySug

[![CircleCI](https://circleci.com/gh/Dynom/TySug.svg?style=svg)](https://circleci.com/gh/Dynom/TySug)
[![Go Report Card](https://goreportcard.com/badge/github.com/Dynom/TySug)](https://goreportcard.com/report/github.com/Dynom/TySug)
[![GoDoc](https://godoc.org/github.com/Dynom/TySug?status.svg)](https://godoc.org/github.com/Dynom/TySug)
[![codecov](https://codecov.io/gh/Dynom/TySug/branch/master/graph/badge.svg)](https://codecov.io/gh/Dynom/TySug)
[![Mentioned in Awesome Go](https://awesome.re/mentioned-badge-flat.svg)](https://github.com/avelino/awesome-go)

TySug is collection of packages, together they form a keyboard layout aware alternative word suggester. It can be used as both a library and a webservice.

![shcool](https://raw.githubusercontent.com/Dynom/TySug/master/docs/shcool.jpg)

The primary supported use-case is to help with spelling mistakes against short popular word lists (e.g. domain names). 
Which is useful in helping to prevent typos in e.g. e-mail addresses, detect spam, phishing ([Typosquatting](https://en.m.wikipedia.org/wiki/Typosquatting)), etc. 

The goal is to provide an extensible library that helps with finding possible spelling errors. You can use it 
out-of-the-box as a library, a webservice or as a set of packages to build your own application.

Currently, it's a fairly naive approach and not (yet) backed by ML.


# Using TySug

You can use TySug as stand-alone webservice to match against a known-list. If you have Docker you'll have it up and running in a few minutes. 

## TL;DR

If you have Docker installed, and you quickly want to tinker, just run:

```bash
docker run --rm -it dynom/tysug:latest
```

_If you don't have Docker, you can download the binary from the [releases](https://github.com/Dynom/TySug/releases) page._

In a different terminal, run:

```bash
curl -s "http://127.0.0.1:1337/list/domains" --data-binary '{"input": "gmail.co"}'
```

## As Webservice

_`curl -s "http://host:port/list/domains" --data-binary '{"input": "gmail.co"}' | jq .`_
```json
{
  "result": "gmail.com",
  "score": 0.9777777777777777,
  "exact_match": false
}
```

- The webservice uses [Jaro-Winkler](https://en.wikipedia.org/wiki/Jaro%E2%80%93Winkler_distance) to calculate similarity.
- The example uses [jq](https://stedolan.github.io/jq/), just omit it if you don't have it installed.


### The path /list/< name >

The name corresponds with a list definition in the [config.toml](https://github.com/Dynom/TySug/blob/master/config.toml). Using this approach the service can be used for various 
types of data. This is both for efficiency (shorter lists to iterate over) and to be more opinionated. when no list by 
that name is found, a 404 is returned.


## As a library
TySug is a collection of stand-alone packages. In each library you can find a README covering the details.
```go
import "github.com/Dynom/TySug/finder"
```
```go
referenceList := []string{"example", "amplifier", "ample"}
ts := finder.New(referenceList, finder.WithAlgorithm(myAlgorithm))

alt, score, exact := ts.Find("exampel")
// alt   = example
// score = 0.9714285714285714
// exact = false (not an exact match in our reference list)
```

### Using a different algorithm

if you want to use a different algorithm, simply wrap your algorithm in a `finder.Algorithm` compatible type and pass 
it as argument to the Finder. You can find inspiration in the unit-tests / examples.

Possible considerations:
 - [Levenshtein](https://en.wikipedia.org/wiki/Levenshtein_distance)
 - [Damerau-Levenshtein](https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance)
 - [LCS](https://en.wikipedia.org/wiki/Longest_common_subsequence_problem)
 - [q-gram](https://en.wikipedia.org/wiki/N-gram)
 - [Cosine](https://en.wikipedia.org/wiki/Cosine_similarity)
 - [Jaccard](https://en.wikipedia.org/wiki/Jaccard_index)
 - [Jaro / Jaro-Winkler](https://en.wikipedia.org/wiki/Jaro%E2%80%93Winkler_distance)
 - [Smith-Waterman](https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorithm)
 - [Sift4](https://siderite.dev/blog/super-fast-and-accurate-string-distance.html) (used in [mailcheck.js](https://github.com/mailcheck/mailcheck))
 
Sources:
 - [joyofdata.de/blog/comparison-of-string-distance-algorithms/](https://www.joyofdata.de/blog/comparison-of-string-distance-algorithms/)

### Dealing with confidence

When adding your own algorithm, you'll need to handle the "confidence" element yourself. By default, TySug's finder will 
handle it just fine, but depending on the scale the algorithm uses you'll need to either normalize the scale or deal 
with the score. 

_Note: Be careful not to introduce bias when converting scale._
```go
var someAlgorithm finder.AlgWrapper = func(a, b string) float64 {

    // Result is, in this instance, the amount of steps taken to achieve equality
    // Algorithms like Jaro produce a value between 0.0 and 1.0
    score := someAlgorithm.CalculateDistance(a, b)
    
    // Finding the longest string
    var ml = len(b)
    if len(a) >= len(b) {
        ml = len(a)
    }
    
    // This introduces a bias. Inputs of longer lengths get a slight favour over shorter ones, causing deletions to weigh less.
    return 1 - (score / float64(ml))
}

sug := finder.New([]list, finder.WithAlgorithm(someAlgorithm))
bestMatch, score := sug.Find(input)
// Here score might be 0.8 for a string of length 10, with 2 mutations
```

Without converting the scale, you'll have no bias, however you need to deal with a range where closer to 0 means fewer changes:
```go
// This will produce a range from (-1 * maximumInputLength) to 0
return -1 * score
```
# Details

## Reference lists

The reference list is a list with known/approved words. TySug's webservice is not optimised to deal with large lists, 
instead it aims for "opinionated" lists. This way you can have a list of domain names or country names. This keeps the 
service snappy and less prone to false-positives.

Large is relative. The size is strongly related to the processing time, longer lists take more time 
[O(N)](http://bigocheatsheet.com/). Test and keep the list within your response-time limits :-). 

### Case-sensitivity

TySug does not normalise words. This means that words are treated in a case-sensitive matter. This is done mostly to
avoid doing unnecessary work in the hot-path. Typically, you'll want to make sure both your lists and your input uses the
same casing.

### Ordering

The reference list order is significant. The first of an equal score wins the election. So you'll want to put more 
common, popular, etc. words first in the list. 

## Keyboard layout awareness

Tysug's webservice is keyboard layout aware. This means that when the input is 'bee5' and the reference list contains the 
words 'beer' and 'beek', the word 'beer' is favoured on a Query-US keyboard.

This happens because of a two-pass approach. In the first pass a list of words is collected with 1 or more words with the
same score. If more than 1 word is found with the same score, the keyboard algorithm is applied. Most string-distance
algorithms factor in the "cost" of reaching equality. The amount of "cost" it takes with one letter difference, in the 
same location within a word (E.g.: bee5 versus beer or beek) is typically the same. Making in the assumption that a 
word is typed by a human on a keyboard and that fingers need to travel a distance to reach certain buttons. Factoring in
this assumption could produce better results in the right context.

# Examples

## Finding common e-mail domain typos

To help people avoid submitting an incorrect e-mail address, one could try the following:

```go
func SuggestAlternative(email string, domains []string) (string, float64) {
    i := strings.LastIndex(email, "@")
    if 0 >= i || i >= len(email) {
        return email, 0
    }

    // Extracting the local and domain parts
    localPart := email[:i]
    hostname := email[i+1:]

    sug, _ := finder.New(domains)
    alternative, score, exact := sug.Find(hostname)

    if exact || score > 0.9 {
        combined := localPart + "@" + alternative
        return combined, score
    }

    return email, score
}
```

# Typos
Dealing with typos is complicated and heavily context dependent.

- Atomic typos -- Typing a (contextual) incorrect, but correctly spelled word (e.g.: _beer_ where you meant: _beet_).
- Intentional typos -- Typing "[teh](https://en.m.wikipedia.org/wiki/Teh)" instead of "the".
- Marking Typos -- Intentional "typos" (e.g.: Bee5^Hr -> _Beer_ or "World Wide Mess^WWeb" -> _World Wide Web_.) 

# Resources

- [https://www.digitalcoding.com/tools/typo-generator.html](https://www.digitalcoding.com/tools/typo-generator.html)
- [http://aspell.net](http://aspell.net) 

# Further reading

- How Difficult is it to Develop a Perfect Spell-checker? A Cross-linguistic Analysis through Complex Network Approach - [https://aclanthology.org/W07-0212/](https://aclanthology.org/W07-0212/) (_[archive.ph link](https://archive.ph/nppY3)_)
- Typographical and Orthographical Spelling Error Correction - [https://aclanthology.org/L00-1169/](https://aclanthology.org/L00-1169/) (_[archive.ph link](https://archive.ph/O74pN)_)
- How to Write a Spelling Corrector - [https://norvig.com/spell-correct.html](https://norvig.com/spell-correct.html)
- Using the Web for Language Independent Spellchecking and Autocorrection - [http://static.googleusercontent.com/media/research.google.com/en/us/pubs/archive/36180.pdf](http://static.googleusercontent.com/media/research.google.com/en/us/pubs/archive/36180.pdf)
- Spellchecking by computer - [https://www.dcs.bbk.ac.uk/..roger/spellchecking.html](https://www.dcs.bbk.ac.uk/~roger/spellchecking.html)

# Contributing

First of all: Awesome!

Before contributing, _please create an issue with the thing you'd like to contribute_.

Any contribution must be provided in the form of a PR and the CI build must pass. Any contribution, when relevant, must have tests proving correctness. The coding-style must be the Go standard, complemented by the community "[Code Review Comments](https://github.com/golang/go/wiki/CodeReviewComments)" laundry list.

# Security

Any security related issues can be submitted as regular issues in the issue tracker. E-mail me directly if you don't want to disclose it publicly.


TySug

High-performance Unicode character width calculation with SWAR optimization, O(1) lookup tables, and ZWJ emoji support

# uniwidth - Modern Unicode Width Calculation for Go

[![Go Version](https://img.shields.io/github/go-mod/go-version/unilibs/uniwidth?label=Go)](https://go.dev/dl/)
[![CI Status](https://github.com/unilibs/uniwidth/actions/workflows/ci.yml/badge.svg)](https://github.com/unilibs/uniwidth/actions)
[![Go Report Card](https://goreportcard.com/badge/github.com/unilibs/uniwidth)](https://goreportcard.com/report/github.com/unilibs/uniwidth)
[![codecov](https://codecov.io/gh/unilibs/uniwidth/branch/main/graph/badge.svg)](https://codecov.io/gh/unilibs/uniwidth)
[![Go Reference](https://pkg.go.dev/badge/github.com/unilibs/uniwidth.svg)](https://pkg.go.dev/github.com/unilibs/uniwidth)
[![License](https://img.shields.io/github/license/unilibs/uniwidth)](LICENSE)
[![Release](https://img.shields.io/github/v/release/unilibs/uniwidth)](https://github.com/unilibs/uniwidth/releases)
[![Stars](https://img.shields.io/github/stars/unilibs/uniwidth)](https://github.com/unilibs/uniwidth/stargazers)

**uniwidth** is a modern, high-performance Unicode width calculation library for Go 1.25+. It provides **3-46x faster** width calculation compared to existing solutions through a 4-tier O(1) lookup architecture, SWAR optimization, and a ZWJ-aware emoji state machine.

## Performance

Based on comprehensive benchmarks vs `go-runewidth`:

- **ASCII strings**: 15-46x faster (SWAR, 8 bytes/iter)
- **CJK strings**: 4-14x faster (O(1) table lookup)
- **Mixed/Emoji strings**: 6-8x faster
- **ZWJ emoji**: Correct width (👨‍👩‍👧‍👦 = 2, ~95 ns)
- **Zero allocations**: 0 B/op, 0 allocs/op for ASCII paths

Run benchmarks yourself: `cd bench && go test -bench=. -benchmem`

## Features

- **3-46x faster** than go-runewidth (proven in benchmarks)
- **All tiers O(1)** — 4-tier lookup with 3-stage hierarchical table (3.8KB)
- **ZWJ-aware** — family emoji, skin tones, flags handled correctly
- **SWAR optimized** — ASCII detection and width counting at 8 bytes/iter
- **Zero allocations** for ASCII strings (no GC pressure)
- **Thread-safe** (immutable design, no global state)
- **Unicode 16.0** support
- **Modern API** (Go 1.25+, functional options pattern)

## Installation

```bash
go get github.com/unilibs/uniwidth
```

**Requirements**: Go 1.25 or later

## Usage

### Basic Usage

```go
package main

import (
    "fmt"
    "github.com/unilibs/uniwidth"
)

func main() {
    // Calculate width of a string
    width := uniwidth.StringWidth("Hello 世界")
    fmt.Println(width) // Output: 10 (Hello=5, space=1, 世界=4)

    // Calculate width of a single rune
    w := uniwidth.RuneWidth('世')
    fmt.Println(w) // Output: 2

    // ASCII-only strings are super fast!
    width = uniwidth.StringWidth("Hello, World!")
    fmt.Println(width) // Output: 13
}
```

### ZWJ Emoji Sequences

```go
// ZWJ family emoji — correctly returns 2, not 8
width := uniwidth.StringWidth("👨‍👩‍👧‍👦")
fmt.Println(width) // Output: 2

// Skin tone modifiers — correctly returns 2, not 4
width = uniwidth.StringWidth("👍🏽")
fmt.Println(width) // Output: 2

// Rainbow flag
width = uniwidth.StringWidth("🏳️‍🌈")
fmt.Println(width) // Output: 2

// Country flags
width = uniwidth.StringWidth("🇺🇸")
fmt.Println(width) // Output: 2
```

### Options API

Configure handling of ambiguous-width characters:

```go
import "github.com/unilibs/uniwidth"

// East Asian locale (ambiguous characters are wide)
opts := []uniwidth.Option{
    uniwidth.WithEastAsianAmbiguous(uniwidth.EAWide),
}
width := uniwidth.StringWidthWithOptions("±½", opts...)
fmt.Println(width) // Output: 4 (each character is 2 columns)

// Neutral locale (ambiguous characters are narrow) - DEFAULT
opts = []uniwidth.Option{
    uniwidth.WithEastAsianAmbiguous(uniwidth.EANarrow),
}
width = uniwidth.StringWidthWithOptions("±½", opts...)
fmt.Println(width) // Output: 2 (each character is 1 column)
```

### Real-World TUI Examples

```go
// Terminal prompt
prompt := "❯ Enter command: "
width := uniwidth.StringWidth(prompt)
fmt.Printf("Prompt width: %d columns\n", width)

// Table cell padding
text := "Hello 世界"
padding := 20 - uniwidth.StringWidth(text)
fmt.Printf("%s%s\n", text, strings.Repeat(" ", padding))

// Truncate to fit terminal width
func truncate(s string, maxWidth int) string {
    width := 0
    for i, r := range s {
        w := uniwidth.RuneWidth(r)
        if width+w > maxWidth {
            return s[:i] + "…"
        }
        width += w
    }
    return s
}
```

## Architecture

### 4-Tier O(1) Lookup

uniwidth uses a multi-tier approach where **all tiers are O(1)**:

1. **Tier 1: ASCII Fast Path** (O(1))
   - Covers ~95% of typical terminal content
   - SWAR `isASCIIOnly()` + `asciiWidth()` process 8 bytes/iter
   - Short strings (< 8 bytes) use fused single-pass loop

2. **Tier 2: Common CJK** (O(1))
   - CJK Unified Ideographs, Hangul Syllables, Hiragana/Katakana
   - Simple range checks for 32,000+ characters

3. **Tier 3: Common Emoji** (O(1))
   - Emoticons, Pictographs, Dingbats, Symbols
   - Range checks for ~1,200 emoji codepoints

4. **Tier 4: 3-Stage Table** (O(1))
   - ROOT[256] → MIDDLE[17×64] → LEAVES[78×32]
   - 2-bit width encoding, 3.8KB total
   - Covers all remaining Unicode codepoints in 3 array lookups

### ZWJ State Machine

Forward-scan state machine for correct emoji sequence handling:
- **3 states**: default → emoji → emojiZWJ
- Handles: ZWJ sequences, skin tone modifiers, variation selectors, flag pairs
- Inspired by Ghostty's approach, adapted for width calculation

### SWAR Optimization

ASCII paths use SIMD Within A Register (SWAR) for high throughput:
- `isASCIIOnly()`: uint64 word AND with `0x8080808080808080` mask
- `asciiWidth()`: Daniel Lemire's underflow trick for control character detection
- Both process 8 bytes per iteration with zero allocations

## Benchmarks

```
goos: windows
goarch: amd64

BenchmarkStringWidth_ASCII_Short     ~7 ns/op     0 B/op   0 allocs/op
BenchmarkStringWidth_ASCII_Medium   ~20 ns/op     0 B/op   0 allocs/op
BenchmarkStringWidth_CJK_Short     ~25 ns/op     0 B/op   0 allocs/op
BenchmarkStringWidth_ZWJ_Family    ~95 ns/op     0 B/op   0 allocs/op
BenchmarkStringWidth_EmojiModifier ~40 ns/op     0 B/op   0 allocs/op
```

Run benchmarks yourself:
```bash
go test -bench=. -benchmem
```

## Use Cases

Perfect for:
- **TUI frameworks** (terminal rendering hot paths)
- **Terminal emulators** (text layout calculations)
- **CLI tools** (table alignment, formatting)
- **Text editors** (cursor positioning, column calculation)
- **Any high-performance text width calculation**

## Migration from go-runewidth

uniwidth provides a compatible API for easy migration:

```go
// Before (go-runewidth)
import "github.com/mattn/go-runewidth"
width := runewidth.StringWidth(s)

// After (uniwidth) - drop-in replacement!
import "github.com/unilibs/uniwidth"
width := uniwidth.StringWidth(s)
```

**Performance improvement**: 3-46x faster, zero code changes!

## Documentation

- [API Reference](https://pkg.go.dev/github.com/unilibs/uniwidth) - Full godoc documentation
- [Benchmark Comparisons](bench/README.md) - Performance comparison vs go-runewidth
- [Architecture Design](docs/ARCHITECTURE.md) - Technical deep dive & design decisions
- [Changelog](CHANGELOG.md) - Version history & upgrade guide
- [Roadmap](ROADMAP.md) - What's next for uniwidth

## Testing

```bash
# Run tests
go test -v

# Run benchmarks
go test -bench=. -benchmem

# Run with coverage
go test -cover
```

Current test coverage: **100%** (library package)

## Development Status

**Current**: v0.2.0

> This library is stable and production-ready. The API is backward-compatible across minor versions. ZWJ emoji sequences, skin tone modifiers, variation selectors, and flag emoji are all handled correctly.

**v0.2.0 Highlights**:
- All 4 lookup tiers are now O(1) (3-stage table replaced binary search)
- SWAR ASCII optimization (8 bytes/iter)
- ZWJ emoji state machine (👨‍👩‍👧‍👦 = width 2)
- Emoji modifier support (👍🏽 = width 2)
- 100% test coverage (library package)
- Automated benchmark CI (regression detection + library comparison)

**Roadmap** (v0.3.0+):
- Non-ASCII StringWidth path optimization
- Profile-Guided Optimization (PGO)
- Explicit SIMD via Go assembly and `archsimd`
- Unicode 17.0 tables

## Contributing

Contributions welcome! This is part of the [unilibs](https://github.com/unilibs) organization - modern Unicode libraries for Go.

## License

MIT License - see [LICENSE](LICENSE) file

## Related Projects

Built by the [Phoenix TUI Framework](https://github.com/phoenix-tui/phoenix) team.

Part of the **unilibs** ecosystem:
- **uniwidth** - Unicode width calculation (this project)
- **unigrapheme** - Grapheme clustering (planned)
- More Unicode utilities coming soon!

## Support

- Issues: [GitHub Issues](https://github.com/unilibs/uniwidth/issues)
- Discussions: [GitHub Discussions](https://github.com/unilibs/uniwidth/discussions)

---

## Special Thanks

**Professor Ancha Baranova** - This project would not have been possible without her invaluable help and support. Her assistance was crucial in bringing uniwidth to life.

---

**Made with care by the Phoenix team** | **Powered by Go 1.25+**


uniwidth

A semantic grep tool using word embeddings to find semantically similar matches. For example, searching for "death" will find "dead", "killing", "murder"

# w2vgrep - Semantic Grep

w2vgrep is a command-line tool that performs semantic searches on text input using word embeddings. It's designed to find semantically similar matches to the query, going beyond simple string matching. Supports multiple languages. The experience is designed to be similar to grep. 


## Example Usage

Search for words similar to "death" in Hemingway's "The Old Man and the Sea" with context and line numbers:

```bash
curl -s 'https://gutenberg.ca/ebooks/hemingwaye-oldmanandthesea/hemingwaye-oldmanandthesea-00-t.txt' \
    | w2vgrep -C 2 -n --threshold=0.55 death
```

Output:
![alt text](demo/image.png)

This command:

    - Fetches the text of "The Old Man and the Sea" from Project Gutenberg Canada
    - Pipes the text to w2vgrep
    - Searches for words semantically similar to "death"
    - Uses a similarity threshold of 0.55 (-threshold 0.55)
    - Displays 2 lines of context before and after each match (-C 2)
    - Shows line numbers (-n)

The output will show matches with their similarity scores, highlighted words, context, and line numbers.

## Features

- Semantic search using word embeddings 
- Configurable similarity threshold
- Context display (before and after matching lines)
- Color-coded output 
- Support for multiple languages 
- Read from files or stdin
- Configurable via JSON file and command-line arguments

## Installation

Two files are absolutely needed: 
1. the w2vgrep binary
2. the vector embedding model file
3. (Optionally, a config.json file to tell w2vgrep where the embedding model is)

**Using install script**:

```bash
# clone
git clone https://github.com/arunsupe/semantic-grep.git
cd semantic-grep

# run install:
#   compiles using the local go compiler, installs in user/bin, 
#   downloads the model to $HOME/.config/semantic-grep
#   makes config.json
bash install.sh
``` 
**Binary**:

1. Download the latest binary release
2. Download a vector embedding model (see below)
3. Optionally, download the config.json to configure model location there (or do this from the command line)

**From source (linux/osx)**:

```bash
# clone
git clone https://github.com/arunsupe/semantic-grep.git
cd semantic-grep

# build
go build -o w2vgrep

# download a word2vec model using this helper script (see "Word Embedding Model" below)
bash download-model.sh
```

## Usage

Basic usage:

./w2vgrep [options] <query> [file]

If no file is specified, w2vgrep reads from standard input.

### Command-line Options
```
-m, --model_path=     Path to the Word2Vec model file. Overrides config file
-t, --threshold=      Similarity threshold for matching (default: 0.7)
-A, --before-context= Number of lines before matching line
-B, --after-context=  Number of lines after matching line
-C, --context=        Number of lines before and after matching line
-n, --line-number     Print line numbers
-i, --ignore-case     Ignore case. 
-o, --only-matching   Output only matching words
-l, --only-lines      Output only matched lines without similarity scores
-f, --file=           Match patterns from file, one pattern per line. Like grep -f.
```

## Configuration

`w2vgrep` can be configured using a JSON file. By default, it looks for `config.json` in the current directory, "$HOME/.config/semantic-grep/config.json" and "/etc/semantic-grep/config.json".


## Word Embedding Model

### Quick start:
`w2vgrep` requires a word embedding model in __binary__ format. The default model loader uses the model file's extension to determine the type (.bin, .8bit.int). A few compatible model files are provided in this repo ([models/](models/)). Download one of the .bin files from the `models/` directory and update the path in config.json.

Note: `git clone` will not download the large binary model files unless git lfs is installed in your machine. If you do not want to install git-lfs, just manually download the model .bin file and place it in the correct folder.


### Support for multiple languages:
Facebook's fasttext group have published word vectors in [157 languages](https://fasttext.cc/docs/en/crawl-vectors.html) - an amazing resource. I want to host these files on my github account, but alas, they are too big and $$$. Therefore, I have provided a small go program, [fasttext-to-bin](model_processing_utils/), that can make `w2vgrep` compatible binary models from this. (note: use the text files with "__.vec.gz__" extension, not the binary ".bin.gz" files)

```bash
# e.g., for a French model:
curl -s 'https://dl.fbaipublicfiles.com/fasttext/vectors-crawl/cc.fr.300.vec.gz' | gunzip -c | ./fasttext-to-bin -input - -output models/fasttext/cc.fr.300.bin

# use it like so:
# curl -s 'https://www.gutenberg.org/cache/epub/17989/pg17989.txt' \
#    | w2vgrep -C 2 -n -t 0.55 \
#           -model_path model_processing_utils/cc.fr.300.bin 'château'
```

### Roll your own:
Alternatively, you can use pre-trained models (like Google's Word2Vec) or train your own using tools like gensim. Note though that there does not seem to be a standardized binary format (google's is different to facebook's fasttext or gensim's default _save()_). For `w2vgrep`, because efficiently loading the large model is key for performance, I have elected to keep the simplest format. 


### Testing the model by finding synonyms
To help troubleshoot the model, I added a `synonym-finder.go` to `./model_processing_utils/`. This program will find similar words to the query word above any threshold in the model.

```bash
# build
cd model_processing_utils
go build synonym-finder.go

#run
synonym-finder -model_path path/to/cc.zh.300.bin -threshold 0.6 合理性

# Output
Words similar to '合理性' with similarity >= 0.60:
科学性 0.6304
合理性 1.0000
正当性 0.6018
公允性 0.6152
不合理性 0.6094
合法性 0.6219
有效性 0.6374
必要性 0.6499
```


## Decreasing the size of the model files
The model files are large (Gigabytes). Each word is typically represented using 300 dimension, 32 bit floating point vectors. Reducing dimensionality, to 100 or 150 dimensions, can produce smaller, memory efficient, faster, more performant models with minimal (maybe even better) accuracy. In `model_processing_utils/reduce-model-size`, I have written a program to reduce model dimensions. This can be used to reduce the size of any word2vec binary model used by w2vgrep. Use this like so:

```bash
# build
cd model_processing_utils/reduce-model-size
go build .

# run on large GoogleNews-vectors-negative300-SLIM.bin model (346MB) to make smaller
# GoogleNews-vectors-negative100-SLIM.bin model (117MB)
./reduce-pca -input ../../models/googlenews-slim/GoogleNews-vectors-negative300-SLIM.bin -output ../../models/googlenews-slim/GoogleNews-vectors-negative100-SLIM.bin

# use this smaller model in w2vgrep like so
curl -s 'https://gutenberg.ca/ebooks/hemingwaye-oldmanandthesea/hemingwaye-oldmanandthesea-00-t.txt' | bin/w2vgrep.linux.amd64 -n -t 0.5 -m models/googlenews-slim/GoogleNews-vectors-negative100-SLIM.bin --line-number death

```


## A word about performance of the different embedding models
Different models define "similarity" differently ([explaination](https://machinelearninginterview.com/topics/natural-language-processing/what-is-the-difference-between-word2vec-and-glove/)). However, for practical purposes, they seem equivalent enough.


## Contributing
Contributions are welcome! Please feel free to submit a Pull Request.


## License and attribution:
The code in this project is licensed under the MIT [License](LICENSE). 

**go-flags package:**

The go-flags package, used by the code in this project, is distributed under the BSD-3-Clause license. Please see the license information https://github.com/jessevdk/go-flags.

**Word2Vec Model**:

This project uses a mirrored version of the word2vec-slim model, which is stored in the `models/googlenews-slim` directory. This model is distributed under the Apache License 2.0. For more information about the model, its original authors, and the license, please see the `models/googlenews-slim/ATTRIBUTION.md` file.

**GloVe word vectors**:

This project uses a processed version of the GloVe word vectors, which is stored in the `models/glove` directory. This work is distributed under the Public Domain Dedication and License v1.0. For more information about the model, its original authors, and the license, please see the `models/glove/ATTRIBUTION.md` file.

**Fasttext word vectors**:

This project uses a processed version of the fasttext word vectors, which is stored in the `models/fasttext` directory. This work is distributed under the Creative Commons Attribution-Share-Alike License 3.0. For more information about the model, its original authors, and the license, please see the `models/fasttext/ATTRIBUTION.md` file.


## Sources of models in the web
- Google's Word2Vec: from https://github.com/mmihaltz/word2vec-GoogleNews-vectors
- A slim version of the above: GoogleNews-vectors-negative300-SLIM.bin.gz model from https://github.com/eyaler/word2vec-slim/
- Stanford NLP group's Global Vectors for Word Representation (glove) model [source](https://nlp.stanford.edu/projects/glove/): binary version is in mirrored in [models/glove/](models/glove/).  
- Facebook fasttext vectors: https://fasttext.cc/docs/en/crawl-vectors.html

w2vgrep

High-performance Aho-Corasick multi-pattern string matching with DFA compilation and SIMD prefilter, up to 7 GB/s throughput (part of [coregx](https://github.com/coregx) ecosystem)

# ahocorasick

[![Go Reference](https://pkg.go.dev/badge/github.com/coregx/ahocorasick.svg)](https://pkg.go.dev/github.com/coregx/ahocorasick)
[![Tests](https://github.com/coregx/ahocorasick/actions/workflows/ci.yml/badge.svg)](https://github.com/coregx/ahocorasick/actions/workflows/ci.yml)
[![Go Report Card](https://goreportcard.com/badge/github.com/coregx/ahocorasick)](https://goreportcard.com/report/github.com/coregx/ahocorasick)
[![codecov](https://codecov.io/gh/coregx/ahocorasick/branch/main/graph/badge.svg)](https://codecov.io/gh/coregx/ahocorasick)
[![Release](https://img.shields.io/github/v/release/coregx/ahocorasick)](https://github.com/coregx/ahocorasick/releases/latest)
[![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](https://opensource.org/licenses/MIT)

High-performance Aho-Corasick multi-pattern string matching for Go.

## Features

- **Up to 7 GB/s throughput** — DFA compilation with SIMD-accelerated prefilter
- **Flat transition table** — fully compiled DFA with premultiplied state IDs
- **SIMD prefilter** — `bytes.IndexByte` skip-ahead for non-matching regions
- **Byte class compression** — reduces memory by grouping equivalent bytes
- **Multiple match semantics** — LeftmostFirst (Perl) and LeftmostLongest (POSIX)
- **Zero dependencies** — pure Go, no cgo
- **Zero allocations** — `IsMatch()` hot path allocates nothing

## Installation

```bash
go get github.com/coregx/ahocorasick
```

Requires Go 1.25+

## Quick Start

```go
package main

import (
    "fmt"
    "github.com/coregx/ahocorasick"
)

func main() {
    // Build automaton from patterns
    ac, _ := ahocorasick.NewBuilder().
        AddStrings([]string{"error", "warning", "fatal"}).
        Build()

    haystack := []byte("[error] something failed")

    // Check if any pattern matches (zero allocation)
    if ac.IsMatch(haystack) {
        fmt.Println("Found a match!")
    }

    // Find first match
    if m := ac.Find(haystack, 0); m != nil {
        fmt.Printf("Found %q at position %d\n",
            haystack[m.Start:m.End], m.Start)
    }

    // Find all non-overlapping matches
    for _, m := range ac.FindAll(haystack, -1) {
        fmt.Printf("Pattern %d: %q\n", m.PatternID, haystack[m.Start:m.End])
    }
}
```

## Performance

Benchmarks on Intel i7-1255U (64KB haystack, 4-7 patterns):

| Method | Throughput | Allocations |
|--------|------------|-------------|
| `IsMatch` (with match) | **7.0 GB/s** | 0 |
| `IsMatch` (no match) | **5.9 GB/s** | 0 |
| `Find` | **3.4 GB/s** | 1 |
| `FindAll` (77B input) | 100 MB/s | 4 |

### How it achieves this

1. **DFA compilation** — all failure transitions pre-computed at build time into a flat `[]uint32` array. Search is a single table lookup per byte: `trans[sid + class]`.
2. **SIMD prefilter** — before running the DFA, `bytes.IndexByte` (SSE2/AVX2 on amd64) scans for pattern start bytes. Skips entire regions where no match is possible.
3. **Skip-ahead on start state** — when the DFA returns to its start state during search, the prefilter re-engages to jump ahead, avoiding byte-by-byte scanning of non-matching text.
4. **Match flag embedding** — the high bit of each transition entry flags match states, enabling single-instruction match detection with no separate lookup.

## API

### Builder

```go
ahocorasick.NewBuilder().
    AddStrings([]string{"foo", "bar"}).  // Add patterns
    SetMatchKind(ahocorasick.LeftmostLongest).  // Optional: POSIX semantics
    Build()  // Returns (*Automaton, error)
```

### Automaton

```go
// Existence check (zero allocation)
ac.IsMatch(haystack []byte) bool

// Find matches
ac.Find(haystack []byte, start int) *Match      // First match from position
ac.FindAt(haystack []byte, start int) *Match    // Match at exact position
ac.FindAll(haystack []byte, n int) []Match      // All non-overlapping (n=-1 for all)
ac.FindAllOverlapping(haystack []byte) []Match  // All including overlaps

// Utilities
ac.Count(haystack []byte) int   // Count non-overlapping matches
ac.PatternCount() int           // Number of patterns
ac.Pattern(id int) []byte       // Get pattern by ID
```

### Match Semantics

```go
LeftmostFirst   // First pattern in list wins (Perl-compatible, default)
LeftmostLongest // Longest pattern wins (POSIX-compatible)
```

## Architecture

```
Builder.Build()
  -> NFA construction (trie + failure links)
  -> DFA compilation (flat transition table, premultiplied state IDs)
  -> Prefilter setup (start byte collection for SIMD scanning)

Search: IsMatch / Find / FindAll
  -> SIMD prefilter (bytes.IndexByte skip-ahead)
  -> DFA traversal (trans[sid + class], one operation per byte)
  -> Match flag check (raw & matchFlag, one AND per byte)
```

## Use Cases

- **Log analysis** — scan for error patterns in log files
- **Content filtering** — detect keywords in text
- **Network security** — signature-based detection
- **DNA sequencing** — find multiple motifs simultaneously
- **Regex acceleration** — as prefilter for `foo|bar|baz` alternations

## Articles

- [Aho-Corasick in Go: Multi-Pattern String Matching at 6 GB/s with Zero Allocations](https://dev.to/kolkov/aho-corasick-in-go-multi-pattern-string-matching-at-6-gbs-with-zero-allocations-2jog) — Deep dive into the DFA compilation, SIMD prefilter, and optimization techniques

## Related Projects

- [coregex](https://github.com/coregx/coregex) — High-performance regex engine (uses this library)
- [BurntSushi/aho-corasick](https://github.com/BurntSushi/aho-corasick) — Rust reference implementation

## License

MIT License — see [LICENSE](LICENSE) for details.


ahocorasick

Functions to get fixed width of the character or string

go-runewidth
============

[![Build Status](https://github.com/mattn/go-runewidth/workflows/test/badge.svg?branch=master)](https://github.com/mattn/go-runewidth/actions?query=workflow%3Atest)
[![Codecov](https://codecov.io/gh/mattn/go-runewidth/branch/master/graph/badge.svg)](https://codecov.io/gh/mattn/go-runewidth)
[![GoDoc](https://godoc.org/github.com/mattn/go-runewidth?status.svg)](http://godoc.org/github.com/mattn/go-runewidth)
[![Go Report Card](https://goreportcard.com/badge/github.com/mattn/go-runewidth)](https://goreportcard.com/report/github.com/mattn/go-runewidth)

Provides functions to get fixed width of the character or string.

Usage
-----

```go
runewidth.StringWidth("つのだ☆HIRO") == 12
```


Author
------

Yasuhiro Matsumoto

License
-------

under the MIT License: http://mattn.mit-license.org/2013


go-runewidth

Common case conversions covering common initialisms

# kace

    go get "github.com/codemodus/kace"

Package kace provides common case conversion functions which take into 
consideration common initialisms.

## Usage

```go
func Camel(s string) string
func Kebab(s string) string
func KebabUpper(s string) string
func Pascal(s string) string
func Snake(s string) string
func SnakeUpper(s string) string
type Kace
    func New(initialisms map[string]bool) (*Kace, error)
    func (k *Kace) Camel(s string) string
    func (k *Kace) Kebab(s string) string
    func (k *Kace) KebabUpper(s string) string
    func (k *Kace) Pascal(s string) string
    func (k *Kace) Snake(s string) string
    func (k *Kace) SnakeUpper(s string) string
```

### Setup

```go
import (
    "fmt"

    "github.com/codemodus/kace"
)

func main() {
    s := "this is a test sql."

    fmt.Println(kace.Camel(s))
    fmt.Println(kace.Pascal(s))

    fmt.Println(kace.Snake(s))
    fmt.Println(kace.SnakeUpper(s))

    fmt.Println(kace.Kebab(s))
    fmt.Println(kace.KebabUpper(s))

    customInitialisms := map[string]bool{
        "THIS": true,
    }
    k, err := kace.New(customInitialisms)
    if err != nil {
        // handle error
    }

    fmt.Println(k.Camel(s))
    fmt.Println(k.Pascal(s))

    fmt.Println(k.Snake(s))
    fmt.Println(k.SnakeUpper(s))

    fmt.Println(k.Kebab(s))
    fmt.Println(k.KebabUpper(s))

    // Output:
    // thisIsATestSQL
    // ThisIsATestSQL
    // this_is_a_test_sql
    // THIS_IS_A_TEST_SQL
    // this-is-a-test-sql
    // THIS-IS-A-TEST-SQL
    // thisIsATestSql
    // THISIsATestSql
    // this_is_a_test_sql
    // THIS_IS_A_TEST_SQL
    // this-is-a-test-sql
    // THIS-IS-A-TEST-SQL
}
```

## More Info

### TODO

#### Test Trie

 Test the current trie.

## Documentation

View the [GoDoc](http://godoc.org/github.com/codemodus/kace)

## Benchmarks

    benchmark                 iter       time/iter   bytes alloc        allocs
    ---------                 ----       ---------   -----------        ------
    BenchmarkCamel4        2000000    947.00 ns/op      112 B/op   3 allocs/op
    BenchmarkSnake4        2000000    696.00 ns/op      128 B/op   2 allocs/op
    BenchmarkSnakeUpper4   2000000    679.00 ns/op      128 B/op   2 allocs/op
    BenchmarkKebab4        2000000    691.00 ns/op      128 B/op   2 allocs/op
    BenchmarkKebabUpper4   2000000    677.00 ns/op      128 B/op   2 allocs/op


kace

Petrovich is the library which inflects Russian names to given grammatical case

![Petrovich](petrovich.png)

Petrovich is the library which inflects Russian names to given grammatical case.

This is the Go port of https://github.com/petrovich.

[![GoDoc](https://godoc.org/github.com/striker2000/petrovich?status.svg)](https://godoc.org/github.com/striker2000/petrovich)
[![Build Status](https://travis-ci.org/striker2000/petrovich.svg?branch=master)](https://travis-ci.org/striker2000/petrovich)
[![Coverage Status](https://coveralls.io/repos/github/striker2000/petrovich/badge.svg?branch=master)](https://coveralls.io/github/striker2000/petrovich?branch=master)
[![Go Report Card](https://goreportcard.com/badge/github.com/striker2000/petrovich)](https://goreportcard.com/report/github.com/striker2000/petrovich)

## Installation

```
go get github.com/striker2000/petrovich
```

## Usage

All functions takes three arguments: name in nominative case, gender and grammatical case.

```go
import "github.com/striker2000/petrovich"

n := petrovich.FirstName("Кузьма", petrovich.Male, petrovich.Genitive)
fmt.Print(n) // "Кузьмы"

n = petrovich.MiddleName("Сергеевич", petrovich.Male, petrovich.Instrumental)
fmt.Print(n) // "Сергеевичем"

n = petrovich.LastName("Петров-Водкин", petrovich.Male, petrovich.Prepositional)
fmt.Print(n) // "Петрове-Водкине"
```

Valid values for gender are `petrovich.Androgynous`, `petrovich.Male` and `petrovich.Female`.

Full list of grammatical cases is in the table below.

| Case                      | Case (in Russian) | Question (in Russian)  |
|---------------------------|-------------------|------------------------|
| `petrovich.Nominative`    | Именительный      | Кто?                   |
| `petrovich.Genitive`      | Родительный       | Кого?                  |
| `petrovich.Dative`        | Дательный         | Кому?                  |
| `petrovich.Accusative`    | Винительный       | Кого?                  |
| `petrovich.Instrumental`  | Творительный      | Кем?                   |
| `petrovich.Prepositional` | Предложный        | О ком?                 |


The Best Go Libraries For Text Processing - Utility/Miscellaneous (9)