textalg

README

• text 模块
  • SliceSame
  • Kmp 文本匹配
  • Aho-Corasick automaton
  • 计算文本编辑距离
  • 计算文本相似度

go get github.com/memory-overflow/go-text-algorithm

text 模块

golang 里面的 strings 库已经有了很多丰富的字符串处理功能，但是都是偏向于基础处理。

text模块提供了一些字符串处理相关的算法能力。

SliceSame

• SliceSame——判断两个字符串数字是否相同。

example: TestSliceSmae

import (
  "testing"

  "github.com/memory-overflow/go-text-algorithm"
)

func TestSliceSmae(t *testing.T) {
	a := []string{"3", "2", "1"}
	same := text.SliceSame(a, a)
	t.Logf("is same: %v", same)
  // test can not change order of a
	t.Log(a)
}

Kmp 文本匹配

通过编辑距离，计算两个文本的相似度。

example: TestTextSim

import (
  "testing"

  "github.com/memory-overflow/go-text-algorithm"
)

func TestKmp(t *testing.T) {
	k := textalg.BuildKmp("a")
	indexs := k.Search("aaaaab") // find "a" in "aaaaab"
	t.Log(indexs)
	k.AppendPatternStr("a")
	indexs = k.Search("aaaaab") // find "aa" in "aaaaab"
	t.Log(indexs)
	k.AppendPatternStr("a")
	indexs = k.Search("aaaaab") // find "aaa" in "aaaaab"
	t.Log(indexs)
	k.AppendPatternStr("b")
	indexs = k.Search("aaaaab") // find "aaab" in "aaaaab"
	t.Log(indexs)
	k.AppendPatternStr("b")
	indexs = k.Search("aaaaab") // find "aaabb" in "aaaaab"
	t.Log(indexs)
	k.ResetPatternStr("ab")
	indexs = k.Search("aaaaab") // find "ab" in "aaaaab"
	t.Log(indexs)
}

Aho-Corasick automaton

ac 自动机是一种多模式串的匹配算法。

一个常见的例子就是给出 n 个单词，再给出一段包含 m 个字符的文章，让你找出有多少个单词在文章里出现过。

比较容易想到的做法是，调用 n 次 strings.Contains(s, xxx)。假设 n 个单词平局长度为 k, 这样处理的算法时间复杂度为 O(n * k * m)。而使用 ac 自动机可以加速上述过程，整体算法时间复杂度只需要 O(n*k + m)。

example: TestActrie

import (
  "testing"

  "github.com/memory-overflow/go-text-algorithm"
)

func TestActrie(t *testing.T) {
  // 在字符串 "哈哈哈哈23434dfgdd" 中找出所有 "哈哈哈", "234"，"dfg" 出现的位置。
  // 使用模式串构建一个 ac 自动机
  ac := text.BuildAcTrie([]string{"哈哈哈", "234", "dfg"})
  // 匹配母串
  list, index := ac.Search("哈哈哈哈23434dfgdd")
  for i, l := range list {
    t.Log(l, index[i])
  }
}

计算文本编辑距离

编辑距离(Edit Distance)：是一个度量两个字符序列之间差异的字符串度量标准，两个单词之间的编辑距离是将一个单词转换为另一个单词所需的单字符编辑（插入、删除或替换）的最小数量。一般来说，编辑距离越小，两个串的相似度越大。

example: TestLevenshtein

import (
  "testing"

  "github.com/memory-overflow/go-text-algorithm"
)

func TestLevenshtein(t *testing.T) {
	dist := text.Levenshtein([]rune("编辑距离测试"), []rune("测试一下距离"))
	t.Logf("dist: %d", dist)
}

计算文本相似度

通过编辑距离，计算两个文本的相似度。

example: TestTextSim

import (
  "testing"

  "github.com/memory-overflow/go-text-algorithm"
)

func TestTextSim(t *testing.T) {
	sim := text.TextSim("编辑距离测试", "测试一下距离")
  t.Logf("sim: %f", sim)
}

Documentation

Index

• func Levenshtein(word1, word2 []rune) int
• func SliceSame(a, b []string) bool
• func TextSim(str1, str2 string) float32
• type AcTrie
  • func BuildAcTrie(words []string) (acTrie *AcTrie)
  • func (ac *AcTrie) Search(s string) (list []string, index []int)
• type Kmp
  • func BuildKmp(patternStr string) *Kmp
  • func (k *Kmp) AppendPatternStr(patternStr string)
  • func (k *Kmp) ResetPatternStr(patternStr string)
  • func (k Kmp) Search(content string) (indexs []int)
• type TrieNode

Functions

func Levenshtein

func Levenshtein(word1, word2 []rune) int

Levenshtein 文本编辑距离

func SliceSame

func SliceSame(a, b []string) bool

SliceSame 对于两个列表的值是否一样

func TextSim

func TextSim(str1, str2 string) float32

TextSim 计算文本的相识度

Types

type AcTrie

type AcTrie struct {
	// contains filtered or unexported fields
}

AcTrie ac自动机匹配字符串算法

func BuildAcTrie

func BuildAcTrie(words []string) (acTrie *AcTrie)

BuildAcTrie 构建一个 ac 自动机

func (*AcTrie) Search

func (ac *AcTrie) Search(s string) (list []string, index []int)

Search 返回匹配的字符串

type Kmp

type Kmp struct {
	// contains filtered or unexported fields
}

Kmp 快速字符串匹配算法，时间复杂度 O(n + m), 其中 n 代表模式串的长度，m 代码匹配母串的长度

func BuildKmp

func BuildKmp(patternStr string) *Kmp

BuildKmp 构建 kmp patternStr 模式串

func (*Kmp) AppendPatternStr

func (k *Kmp) AppendPatternStr(patternStr string)

AppendPatternStr 扩充模式串长度

func (*Kmp) ResetPatternStr

func (k *Kmp) ResetPatternStr(patternStr string)

ResetPatternStr 重置模式串

func (Kmp) Search

func (k Kmp) Search(content string) (indexs []int)

Search 返回所有 pattern 在 content 中出现的开始位置的 index

type TrieNode

type TrieNode struct {
	// contains filtered or unexported fields
}

TrieNode ac自动机节点