matching

package
v0.0.0-...-46105d7 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Jun 5, 2024 License: GPL-3.0 Imports: 1 Imported by: 0

README

Zadanie na 4. zajęcia

Celem dzisiejszych zajęć jest:

  • Zapoznać się z "przybliżonymi" wersjami algorytmu Shift-Or. Te wersje algorytmu Shift-Or znajdują takie podłańcuchy tekstu, których odległość Hamminga lub odległość Levenshteina od wzorca nie przekracza danej stałej, w naszym przypadku stałej 2.

  • Przetestować pakiet, który służy do znajdowania wielu wzorców w tekście algorytmem Aho-Corasick. Napiszą państwo testy jednostkowe, które porównają wynik działania algorytmu Aho-Corasick z wynikiem działania wielokrotnie uruchomionego algorytmu Boyera-Moore'a, oraz testy wydajnościowe, które porównają czas działania algorytmu Aho-Corasick z czasem działania wielokrotnie uruchomionego algorytmu Boyera-Moore'a.

  1. Proszę wykonać polecenie
go get github.com/BobuSumisu/aho-corasick
  1. Proszę pobrać z serwisu https://wolnelektury.pl dowolną książkę w formacie .txt

Wersje algorytmu Shift-Or

  1. Proszę napisać funkcje TestFuzzyShiftOrH i TestFuzzyShiftOrL. W obu tych funkcjach proszę kolejno:
  • wczytać do zmiennej text zawartość pobranej książki, korzystając z funkcji os.ReadFile (https://pkg.go.dev/os#ReadFile)

  • przypisać do zmiennej pat jakiś 5- lub 6-literowy wyraz jako wartość typu []byte, czyli na przykład pat := []byte("domek")

  • przypisać do zmiennej got pusty wycinek złożony z łańcuchów: got := []string{}

  • wywołać odpowiednio funkcję FuzzyShiftOrH lub FuzzyShiftOrL, podając jako jej trzeci argument funkcję anonimową odpowiednio func(n int) { got = append(got, string(text[n:n+len(pat)])) } i func(n int) { got = append(got, string(text[n-len(pat)-1:n+1])) }; ciała tych funkcji anonimowych są różne, ponieważ funkcja FuzzyShiftOrH zwraca indeks początku wystąpienia wzorca w tekście, a funkcja FuzzyShiftOrL zwraca indeks końca wystąpienia wzorca w tekście

  • wypisać zawartość wycinka got, korzystając z funkcji fmt.Printf i specyfikatora formatu %v; niech funkcje TestFuzzyShiftOrH i TestFuzzyShiftOrL nie robią żadnych testów, tylko wypisują zawartość wycinka got

  • wykonać polecenie go test i zobaczyć wyniki działania tych dwóch funkcji

  • przepisać kilka znalezionych przykładów do arkusza http://tiny.cc/at-lab4-2024

Algorytm Aho-Corasick

  1. Proszę wypełnić zmienną globalną words wszystkimi formami odmiany wybranego rzeczownika lub przymiotnika.

  2. Proszę napisać funkcję TestAhoCorasick. W tej funkcji proszę kolejno:

  • wczytać do zmiennej text zawartość pobranej książki, korzystając z funkcji os.ReadFile (https://pkg.go.dev/os#ReadFile)

  • zbudować drzewo trie, z którego korzysta algorytm Aho-Corasick:

builder := ahocorasick.NewTrieBuilder()
builder.AddStrings(words)
trie := builder.Build()
  • wyszukać algorytmem Aho-Corasick wszystkie wystąpienia w tekście wszystkich wzorców zapisanych w zmiennej words i przypisać je do zmiennej matches:
matches := trie.MatchString(string(text))
  • napisać część funkcji, która wypełnia n-ty element tablicy wycinków got numerami tych pozycji w tekście, na których zaczynają się wystąpienia n-tego elementu wycinka words, znalezione algorytmem Aho-Corasick; proszę zmienić wartość stałej 12 na liczbę równą długości wycinka words:
var got [12][]int64
for _, m := range matches {
	got[m.Pattern()] = append(got[m.Pattern()], m.Pos())
}
  • napisać część funkcji, która która wypełnia n-ty element tablicy wycinków want numerami tych pozycji w tekście, na których zaczynają się wystąpienia n-tego elementu wycinka words, znalezione algorytmem Boyera-Moore'a; proszę zmienić wartość stałej 12 na liczbę równą długości wycinka words:
var want [12][]int64
for i, pat := range words {
	BoyerMoore([]byte(pat), text, func(n int) {
		want[i] = append(want[i], int64(n))
	})
}
  • napisać część funkcji, która porównuje tablicę wycinków got z tablicą wycinków want:
for i := range got {
	if !slices.Equal(got[i], want[i]) {
		t.Errorf("got[%d] == %v want %v", i, got[i], want[i])
	}
}
  • dla zaspokojenia ciekawości można dopisać do tej funkcji fragment:
fmt.Printf("Znalezione wystąpienia wyrazów %v:\n%v\n", words, got)
  1. Proszę napisać funkcję BenchmarkAhoCorasick. W tej funkcji proszę kolejno:
  • wczytać do zmiennej text zawartość pobranej książki, korzystając z funkcji os.ReadFile (https://pkg.go.dev/os#ReadFile)

  • przypisać do zmiennej stext zawartość zmiennej text jako łańcuch:

stext := string(text)
  • wyzerować stoper, wywołując funkcję b.ResetTimer

  • przepisać poniższy fragment kodu, który mierzy czas budowania drzewa trie z wzorców i wyszukiwania tych wzorców w tekście:

for i := 0; i < b.N; i++ {
	builder := ahocorasick.NewTrieBuilder()
	builder.AddStrings(words)
	trie := builder.Build()
	trie.MatchString(stext)
}
  1. Proszę napisać funkcję BenchmarkBoyerMoore, żeby móc porównywać czas wyszukiwania wszystkich wzorców algorytmem Aho-Corasick i wielokrotnie uruchamianym algorytmem Boyera-Moore'a. Funkcja BenchmarkBoyerMoore jest podobna do funkcji BenchmarkAhoCorasick z tym, że wyszukiwanie wszystkich wzorców w tekście jest zakodowane tak:
for _, pat := range words {
	BoyerMoore([]byte(pat), text, func(int){})
}
  1. Proszę porównać czas wyszukiwania wszystkich wzorców algorytmem Aho-Corasick i algorytmem Boyera-Moore'a i wpisać go do arkusza http://tiny.cc/at-lab4-2024 — przypominam, że testy wydajnościowe uruchamia się poleceniem go test -bench=.

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func BoyerMoore

func BoyerMoore(pat, text []byte, output func(int))

BoyerMoore wywołuje `output(i)` dla każdego takiego `i`, że `slices.Equal(text[i:i+len(pat)], pat)`

func FuzzyShiftOrH

func FuzzyShiftOrH(pat, text []byte, output func(int))

FuzzyShiftOrH wywołuje funkcję `output(i)` dla każdego takiego indeksu `i`, że `text[i:i+len(pat)]` różni się od `pat` co najwyżej na 2 pozycjach

func FuzzyShiftOrL

func FuzzyShiftOrL(pat, text []byte, output func(int))

FuzzyShiftOrL wywołuje funkcję `output(i)` dla każdego takiego indeksu `i`, że odległość Levenshteina między pewnym wycinkiem `text[...:i+1]` a wzorcem `pat` wynosi co najwyżej 2

Types

This section is empty.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL