intel / intel/hyperscan

Approximate match (edit distance and hamming distance)

Open
#412 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
5.5k
Forks
816
Avg merge
4d 21h
Merged PRs (30d)
2

Description

Hi,
I am studying about edit distance and hamming distance in my hyperscan env.
but it's a little hard for me to understand how to find whitch one is the best matching.
my example like this

```go
type ScanContext struct {
*bytes.Buffer
data []byte
}

func main() {
// distance = 3
// one of pattern is like "tipsytemasagronomicos.com"
patterns = append(patterns, hs.NewPattern(pattern, hs.Caseless, hs.EditDistance(uint32(distance))))
...

// create hyperscan db
hsdb, err := hs.NewBlockDatabase(patterns...)
scratch, err := hs.NewScratch(*hsdb)
...

buf := new(bytes.Buffer)
input:= "13243412tipsytemasagr0n0mic0s.c0m"
if err := (*d.HsDatabase).Scan([]byte(input), scratch, handleMatch, ScanContext{buf, []byte(input)}); err != nil {
fmt.Println(err)
}
fmt.Printf("match: %s\n", buf.String())
if len(buf.String()) > 0 {
log.Println("Levenshtein distance match:", true)
}
}

func handleMatch(id uint, from, to uint64, flags uint, data interface{}) error {
ctx, _ := data.(ScanContext)
fmt.Println("from:", from)
fmt.Println("to:", to)
fmt.Println("data:", string(ctx.data))
if from < to {
_, err := fmt.Fprintf(ctx.Buffer, "%s", ctx.data[from:to])
if err != nil {
return err
}
}

return nil
}
```
The result is like that:
![image](https://github.com/intel/hyperscan/assets/33200478/33787bae-be9d-4e73-a30f-32b122f00553)
![image](https://github.com/intel/hyperscan/assets/33200478/bb48cd9b-9d50-47b7-bac1-d049696670dd)

So, how can I do for next step, can you guys show me some example about the approximate match?

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.