oo

Documentation

Index

• Variables
• func EncodeGrammar(data []uint32, capacity int) ([]byte, int)
• func IsValidNt(ntCounter int) bool
• type CompNt
• type File
  • func NewFile(name string, data []uint32) *File
  • func (file *File) CompleteChoice(choice []bool) []bool
  • func (file *File) Construct()
  • func (file *File) GetDistances(d []int, p []*NonTerminal, choice []bool, curNtId int) (start, end int)
  • func (file *File) GetDistancesPart(d []int, choice []bool, curNtId, start, end int)
  • func (file *File) GetOptimalLength(d []int, choice []bool, ntNum int) int
  • func (file *File) Path(choice []bool) []int
  • func (file *File) PathReconstruction(p []*NonTerminal, end, length int, fData func(int, int, uint32), ...)
  • func (file *File) PlainReconstruction(choice []bool) []uint32
  • func (file *File) Score(choice []bool) int
  • func (file *File) ScoreCleanUp(choice []bool) (int, []bool)
  • func (file *File) ScoreExtended(choice []bool, ntIds []int) ([]uint32, int)
  • func (file *File) ScoreWithReconstruction(currentChoice []bool) ([]byte, int)
  • func (file *File) ShortestPath(activeNts []bool, ntNum int, ntNumbering []int) []uint32
  • func (file *File) ShortestPathAdd(d []int, p []*NonTerminal, inNt []int, choice []bool, ntNum int, ...)
  • func (file *File) ShortestPathCount(d []int, p []*NonTerminal, activeNts []bool, ntNum int, ntCounts []int) int
  • func (file *File) ShortestPathOccurences(d []int, p []*NonTerminal, alreadyChecked []bool, activeNts []bool, ntNum int, ...)
• type Graph
• type Individual
• type NonTerminal
• type Solution
• type SuffixTree
  • func (t *SuffixTree) CreateGraph(graph Graph, nts *[]*NonTerminal, depth int)
  • func (t *SuffixTree) Insert(data []uint32, startIndex, currentIndex int)
  • func (t *SuffixTree) StartsWith(data []uint32) uint32

Variables

var (
	OoCounter *int64 = new(int64)
)

Functions

func EncodeGrammar

func EncodeGrammar(data []uint32, capacity int) ([]byte, int)

Transformation from the internal encoding to the specified one

func IsValidNt

func IsValidNt(ntCounter int) bool

Avoid critical NT encodings

Types

type CompNt

type CompNt struct {
	Id     int
	Length int
}

type File

type File struct {
	Name         string
	Data         []uint32
	Size         int
	Graph        Graph
	NonTerminals []*NonTerminal
	NtCount      int
}

The main data structure for the internal representation of the given problem

func NewFile

func NewFile(name string, data []uint32) *File

func (*File) CompleteChoice

func (file *File) CompleteChoice(choice []bool) []bool

Completes the choice by computing the MGP on the chosen non-terminals and adds the used non-terminals

func (*File) Construct

func (file *File) Construct()

Get all repeats (possible non-terminals) and construct a graph for occurrence optimization with all of them.

func (*File) GetDistances

func (file *File) GetDistances(d []int, p []*NonTerminal, choice []bool, curNtId int) (start, end int)

Here is the actual computation of the shortest path distances. p can be nil

func (*File) GetDistancesPart

func (file *File) GetDistancesPart(d []int, choice []bool, curNtId, start, end int)

func (*File) GetOptimalLength

func (file *File) GetOptimalLength(d []int, choice []bool, ntNum int) int

Returns only the length of the shortest path in a non-terminal.

func (*File) Path

func (file *File) Path(choice []bool) []int

Returns the path used by ACO, only for the initial non-terminal for now

func (*File) PathReconstruction

func (file *File) PathReconstruction(p []*NonTerminal, end, length int, fData func(int, int, uint32),
	fNt func(int, int, *NonTerminal))

Reconstruction of the shortest path with the given shortest distances. Calls the given functions on each step of the shortest path so that this function can be used as a generic helper.

func (*File) PlainReconstruction

func (file *File) PlainReconstruction(choice []bool) []uint32

func (*File) Score

func (file *File) Score(choice []bool) int

Non-concurrent score function

func (*File) ScoreCleanUp

func (file *File) ScoreCleanUp(choice []bool) (int, []bool)

func (*File) ScoreExtended

func (file *File) ScoreExtended(choice []bool, ntIds []int) ([]uint32, int)

Additional to the score, all shortest paths are computed.

func (*File) ScoreWithReconstruction

func (file *File) ScoreWithReconstruction(currentChoice []bool) ([]byte, int)

func (*File) ShortestPath

func (file *File) ShortestPath(activeNts []bool, ntNum int, ntNumbering []int) []uint32

Returns the shortest path in a non-terminal (in the internal encoding).

func (*File) ShortestPathAdd

func (file *File) ShortestPathAdd(d []int, p []*NonTerminal, inNt []int, choice []bool, ntNum int, ntAddBenefit []int, next []int)

Computes the heuristic benefits of adding a non-terminal for all non-terminals that are not used. It is basically computed whether adding at any possible point would shorten the shortest path. However, this is only done if the 'new non-terminal' does not interfere with already used ones.

func (*File) ShortestPathCount

func (file *File) ShortestPathCount(d []int, p []*NonTerminal, activeNts []bool, ntNum int, ntCounts []int) int

Returns the shortest path in a non-terminal (in the internal encoding) and additionally computes how often each non-terminal is used in this shortest path.

func (*File) ShortestPathOccurences

func (file *File) ShortestPathOccurences(d []int, p []*NonTerminal, alreadyChecked []bool, activeNts []bool, ntNum int,
	ntLength []int, toCalculate [][]int, activeNtCount int)

Determines which other non-terminals are used in the shortest path of the given non-terminal. The combined results can then be used to minimize the computations for determining the score without a non-terminal that was used before.

type Graph

type Graph [][]CompNt

The graph used for occurrence optimization

type Individual

type Individual struct {
	Score  int
	Choice []bool
}

type NonTerminal

type NonTerminal struct {
	Id     int
	Start  int
	Length int
	Count  int
}

type Solution

type Solution struct {
	Score   int
	Choice  []bool
	NoScore bool
}

type SuffixTree

type SuffixTree struct {
	StartIndex  int
	EndIndex    int
	Occurrences []int
	Children    []*SuffixTree
}

func (*SuffixTree) CreateGraph

func (t *SuffixTree) CreateGraph(graph Graph, nts *[]*NonTerminal, depth int)

Creates a graph that can be used for occurrence optimization out of the suffix tree. The nodes of the graph are all characters in the input and for each node the outgoing edges (non-terminals starting there) are added.

func (*SuffixTree) Insert

func (t *SuffixTree) Insert(data []uint32, startIndex, currentIndex int)

Inserts a new suffix into the tree. This is done in a compressed way and means that only one split is done per insertion.

func (*SuffixTree) StartsWith

func (t *SuffixTree) StartsWith(data []uint32) uint32

Checks wheter the node starts with the given character