lcs

Documentation

Overview

Package lcs ...

Index

• Variables
• func Split(s string) []string
• type Comparable
• type Element
  • func (e Element) String() string
• type Indices
• type Sequence
  • func NewChars(s string) Sequence
  • func NewLines(s string) Sequence
  • func NewWords(words []string) Sequence
  • func StandardLCS(xs, ys Sequence) Sequence
  • func (xs Sequence) Histogram() map[string][]int
  • func (xs Sequence) IsSubsequenceOf(ys Sequence) bool
  • func (xs Sequence) Occurrence(y Sequence) [][]int
  • func (xs Sequence) String() string
  • func (xs Sequence) Sub(idx Indices) Sequence
  • func (xs Sequence) YadLCS(ctx context.Context, ys Sequence) Indices

Variables

var SplitKey = struct{}{}

SplitKey for context

Functions

func Split

func Split(s string) []string

Split a line into words

Types

type Comparable

type Comparable interface {
	// String for comparison, such as the hash
	String() string
}

Comparable interface

type Element

type Element string

Element of a line, a word, or a character

func (Element) String

func (e Element) String() string

String returns the full content

type Indices

type Indices []int

Indices is the index list of items in xs that forms the LCS between xs and ys.

type Sequence

type Sequence []Comparable

Sequence list

func NewChars

func NewChars(s string) Sequence

NewChars from string

func NewLines

func NewLines(s string) Sequence

NewLines from string. It will split the s via newlines.

func NewWords

func NewWords(words []string) Sequence

NewWords from string list

func StandardLCS

func StandardLCS(xs, ys Sequence) Sequence

StandardLCS implementation for testing purpose only, because it's very inefficient. https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#LCS_function_defined.

func (Sequence) Histogram

func (xs Sequence) Histogram() map[string][]int

Histogram of each Comparable

func (Sequence) IsSubsequenceOf

func (xs Sequence) IsSubsequenceOf(ys Sequence) bool

IsSubsequenceOf returns true if x is a subsequence of y

func (Sequence) Occurrence

func (xs Sequence) Occurrence(y Sequence) [][]int

Occurrence returns the position of each element of y in x.

func (Sequence) String

func (xs Sequence) String() string

String interface

func (Sequence) Sub

func (xs Sequence) Sub(idx Indices) Sequence

Sub from p, it will automatically decompress the compressed p.

func (Sequence) YadLCS

func (xs Sequence) YadLCS(ctx context.Context, ys Sequence) Indices

YadLCS returns the x index of each Comparable that are in the YadLCS between x and y. The complexity is O(M * log(L)), M is the number of char matches between x and y, L is the length of LCS. The worst memory complexity is O(M), but usually it's much less.

The advantage of this algorithm is it's easy to understand and implement. It converts the LCS problem into problems that are familiar to us, such as LIS, binary-search, object-recycle, etc., which give us more room to do the optimization for each streamline.