Golang Algorithm - Rabin Karp

 

Rabin-Karp 알고리즘

 

이 코드는 Go 언어로 구현된 문자열 검색 함수를 보여주는 코드입니다. 이 함수는 하나의 텍스트 문자열과 검색할 패턴 문자열의 목록을 입력 받고, 각 패턴 문자열이 텍스트 문자열에 존재하는지 여부를 검색합니다. 그리고 존재하는 패턴 문자열의 목록을 반환합니다.

 

여기에는 몇 가지 함수가 있습니다:

• Search(txt string, patterns []string) []string: 이 함수는 텍스트 문자열과 패턴 문자열의 슬라이스를 받아들입니다. 이 함수는 indices() 함수를 사용하여 문자열에서 패턴 문자열의 존재 여부를 확인하고, 존재하는 패턴 문자열의 목록을 반환합니다.
• indices(txt string, patterns []string) map[int]int: 이 함수는 문자열에서 패턴 문자열의 존재 여부를 확인합니다. 이 함수는 hashPatterns() 함수를 사용하여 패턴 문자열을 해싱하고, hash() 함수를 사용하여 문자열을 해싱합니다. 그리고 해싱된 패턴 문자열을 사용하여 해시 테이블에서 해당 패턴 문자열을 찾습니다.
• hash(s string) uint32: 이 함수는 문자열을 해싱하는 함수입니다. 문자열의 각 문자를 사용하여 해시 값을 계산합니다.
• hashPatterns(patterns []string, l int) map[uint32][]int: 이 함수는 패턴 문자열을 해싱하는 함수입니다. 패턴 문자열을 사용하여 해시 값을 계산하고, 해시 값을 사용하여 패턴 문자열을 해시 테이블에서 찾습니다.
• minLen(patterns []string) int: 이 함수는 패턴 문자열 중 가장 짧은 문자열의 길이를 반환합니다.

main() 함수는 검색할 텍스트 문자열과 패턴 문자열의 목록을 정의하고 Search() 함수를 호출하여 검색 결과를 출력합니다.

이 코드는 문자열 검색에 널리 사용되는 Rabin-Karp 알고리즘을 구현한 것입니다. Rabin-Karp 알고리즘은 각 문자열의 해시 값을 빠르게 계산하여 문자열을 비교하는 데 사용됩니다.

 

 

 

라빈카르프 알고리즘은 문자열에서 패턴을 찾기 위해 해싱을 사용하는 문자열 검색 알고리즘이다. 라빈-카르프 문자열 검색 알고리즘 구현을 위한 Go 프로그램의 소스 코드는 다음과 같습니다.

package main

import (
	"fmt"
)

const base = 16777619

func Search(txt string, patterns []string) []string {
	in := indices(txt, patterns)
	matches := make([]string, len(in))
	i := 0
	for j, p := range patterns {
		if _, ok := in[j]; ok {
			matches[i] = p
			i++
		}
	}

	return matches
}

func indices(txt string, patterns []string) map[int]int {
	n, m := len(txt), minLen(patterns)
	matches := make(map[int]int)

	if n < m || len(patterns) == 0 {
		return matches
	}

	var mult uint32 = 1 // mult = base^(m-1)
	for i := 0; i < m-1; i++ {
		mult = (mult * base)
	}

	hp := hashPatterns(patterns, m)
	h := hash(txt[:m])
	for i := 0; i < n-m+1 && len(hp) > 0; i++ {
		if i > 0 {
			h = h - mult*uint32(txt[i-1])
			h = h*base + uint32(txt[i+m-1])
		}

		if mps, ok := hp[h]; ok {
			for _, pi := range mps {
				pat := patterns[pi]
				e := i + len(pat)
				if _, ok := matches[pi]; !ok && e <= n && pat == txt[i:e] {
					matches[pi] = i
				}
			}
		}
	}
	return matches
}

func hash(s string) uint32 {
	var h uint32
	for i := 0; i < len(s); i++ {
		h = (h*base + uint32(s[i]))
	}
	return h
}

func hashPatterns(patterns []string, l int) map[uint32][]int {
	m := make(map[uint32][]int)
	for i, t := range patterns {
		h := hash(t[:l])
		if _, ok := m[h]; ok {
			m[h] = append(m[h], i)
		} else {
			m[h] = []int{i}
		}
	}

	return m
}

func minLen(patterns []string) int {
	if len(patterns) == 0 {
		return 0
	}

	m := len(patterns[0])
	for i := range patterns {
		if m > len(patterns[i]) {
			m = len(patterns[i])
		}
	}

	return m
}

func main() {
	txt := "Australia is a country and continent surrounded by the Indian and Pacific oceans."
	patterns := []string{"and", "the", "surround", "Pacific", "Germany"}
	matches := Search(txt, patterns)
	fmt.Println(matches)
}

 

go 입출력코드

 go run rabinKarp.go 
[and the surround Pacific]