自己寫個搜尋引擎
摘要：
搜尋引擎最核心的地方在於倒排索引，而倒排索引其實並不是一種具體的資料結構，確切的來說是一類。
這個實現中使用Golang中的map
來做倒排索引，全部程式碼如下：
package main
import (
"io/ioutil"
"...
搜尋引擎最核心的地方在於倒排索引，而倒排索引其實並不是一種具體的資料結構，確切的來說是一類。
這個實現中使用Golang中的map
來做倒排索引，全部程式碼如下：
package main
import (
"io/ioutil"
"log"
"os"
)
// Index 倒排索引索引項
type Index struct {
DocumentName string
Offsetint
}
// ToParsingFile 待索引的檔案
type ToParsingFile struct {
FileName string
Content string
}
// ReverseIndex 單個倒排索引具體
type ReverseIndex map[string][]Index
// Blacklist 倒排索引key的黑名單
type Blacklist map[string]bool
// Ignorelist 忽略字元列表
type Ignorelist map[rune]bool
func readFile(fileName string) (string, error) {
contentBytes, err := ioutil.ReadFile(fileName)
if err != nil {
log.Printf("open file failed with error: %v\n", err)
return "", err
}
return string(contentBytes), nil
}
func parse(ignorelist Ignorelist, fileName, content string) ReverseIndex {
reverseFile := make(ReverseIndex)
lastIndex := 0
for i, c := range(content) {
if _, ok := ignorelist[c]; ok {
newWord := string(content[lastIndex:i])
reverseFile[newWord] = append(reverseFile[newWord], Index{fileName, lastIndex})
lastIndex = i + 1
}
}
return reverseFile
}
// 合併多個倒排索引並且剔除blacklist中的key
func mergeReverseIndex(blacklist Blacklist, args ...ReverseIndex) ReverseIndex {
result := make(ReverseIndex)
for _, arg := range(args) {
for k, vs := range(arg) {
// 忽略黑名單中的key
if _, ok := blacklist[k]; ok {
continue
}
// 忽略連續斷字元組成的
if len(k) == 0 {
continue
}
// TODO: write myself a `extend` function for Golang slice
for _, v := range(vs) {
result[k] = append(result[k], v)
}
}
}
return result
}
func getDocumentNames(reverseFile ReverseIndex, keyWord string) map[string]bool {
resultMap := make(map[string]bool)
indexList, ok := reverseFile[keyWord]
if !ok {
return resultMap
}
for _, index := range(indexList) {
resultMap[index.DocumentName] = true
}
return resultMap
}
func makeSubSetOf(map1, map2 map[string]bool) map[string]bool {
var longer, shorter map[string]bool
resultMap := make(map[string]bool)
if len(map1) > len(map2) {
longer = map1
shorter = map2
} else {
longer = map2
shorter = map1
}
for k := range(shorter) {
if _, ok := longer[k]; ok {
resultMap[k] = true
}
}
return resultMap
}
// 搜尋，目前的檢索方案為：
// 檢索出每個關鍵字所在的文章
// 對關鍵字做交集處理
// 取出所有關鍵字都存在的文章然後返回
func search(reverseFile ReverseIndex, keyWords ...string) []string {
result := make([]string, 0)
var finalDocumentNames map[string]bool
for _, keyWord := range(keyWords) {
documentNames := getDocumentNames(reverseFile, keyWord)
if finalDocumentNames == nil {
finalDocumentNames = documentNames
}
finalDocumentNames = makeSubSetOf(finalDocumentNames, documentNames)
}
for doc := range(finalDocumentNames) {
result = append(result, doc)
}
return result
}
func main() {
contents := make([]ToParsingFile, 0)
files, err := ioutil.ReadDir("./docs")
if err != nil {
log.Panicf("read dir(./docs) failed, aborting...")
}
for _, file := range(files) {
fileName := file.Name()
content, err := readFile("./docs/" + fileName)
if err != nil {
log.Panicf("read file(%s) failed!", fileName)
}
contents = append(contents, ToParsingFile{fileName, content})
}
blacklist := Blacklist{"a": false, "is": false}
ignorelist := Ignorelist{
' ': false, '\t': false, '\n': false, '\r': false, ',': false, '.': false,
'"': false, ':': false, '`': false, '(': false, ')': false, '[': false, ']': false,
'{': false, '}': false, '-': false, '_': false, '+': false, '=': false,
'\\': false, '|': false, '\'': false, '<': false, '>': false, '$': false,
}
var reverseFiles []ReverseIndex
for _, toParsingFile := range(contents) {
reverseFiles = append(reverseFiles, parse(ignorelist, toParsingFile.FileName, toParsingFile.Content))
}
reverseFile := mergeReverseIndex(blacklist, reverseFiles...)
log.Printf("we're going to create reverse index")
for k, vs := range reverseFile {
log.Printf("Key: %s -> ", k)
for _, v := range vs {
log.Printf("in doc %s with offset %d, ", v.DocumentName, v.Offset)
}
}
log.Printf("looping done")
keyWords := os.Args[1:]
searchResults := search(reverseFile, keyWords...)
log.Printf("========================= Search Engine =================\n")
log.Printf("searing %v...\n", keyWords)
for _, searchResult := range(searchResults) {
log.Printf("in file: %s\n", searchResult)
}
log.Printf("done.\n")
}
執行日誌：
$ go run reverse_file.go bigbang 2017/06/02 23:12:19 we're going to create reverse index 2017/06/02 23:12:19 Key: inherited -> 2017/06/02 23:12:19 in doc dev.rst with offset 297, 2017/06/02 23:12:19 Key: are -> 2017/06/02 23:12:19 in doc dev.rst with offset 16, 2017/06/02 23:12:19 Key: Installation -> 2017/06/02 23:12:19 in doc user.rst with offset 105, 2017/06/02 23:12:19 Key: about -> 2017/06/02 23:12:19 in doc user.rst with offset 78, 2017/06/02 23:12:19 Key: Using -> 2017/06/02 23:12:19 in doc user.rst with offset 266, 2017/06/02 23:12:19 Key: User -> 2017/06/02 23:12:19 in doc user.rst with offset 0, 2017/06/02 23:12:19 Key: of -> 2017/06/02 23:12:19 in doc dev.rst with offset 95, 2017/06/02 23:12:19 in doc user.rst with offset 36, 2017/06/02 23:12:19 in doc user.rst with offset 560, 2017/06/02 23:12:19 Key: method -> 2017/06/02 23:12:19 in doc dev.rst with offset 77, 2017/06/02 23:12:19 Key: by -> 2017/06/02 23:12:19 in doc user.rst with offset 337, 2017/06/02 23:12:19 Key: use -> 2017/06/02 23:12:19 in doc user.rst with offset 91, 2017/06/02 23:12:19 in doc user.rst with offset 309, 2017/06/02 23:12:19 Key: using -> 2017/06/02 23:12:19 in doc user.rst with offset 582, 2017/06/02 23:12:19 Key: set -> 2017/06/02 23:12:19 in doc user.rst with offset 468, 2017/06/02 23:12:19 in doc user.rst with offset 698, 2017/06/02 23:12:19 Key: for -> 2017/06/02 23:12:19 in doc dev.rst with offset 28, 2017/06/02 23:12:19 in doc dev.rst with offset 119, 2017/06/02 23:12:19 Key: loop -> 2017/06/02 23:12:19 in doc dev.rst with offset 231, 2017/06/02 23:12:19 in doc user.rst with offset 323, 2017/06/02 23:12:19 in doc user.rst with offset 381, 2017/06/02 23:12:19 in doc user.rst with offset 478, 2017/06/02 23:12:19 in doc user.rst with offset 567, 2017/06/02 23:12:19 in doc user.rst with offset 655, 2017/06/02 23:12:19 in doc user.rst with offset 679, 2017/06/02 23:12:19 in doc user.rst with offset 708, 2017/06/02 23:12:19 in doc user.rst with offset 713, 2017/06/02 23:12:19 Key: undoc -> 2017/06/02 23:12:19 in doc dev.rst with offset 279, 2017/06/02 23:12:19 Key: bigbang -> 2017/06/02 23:12:19 in doc dev.rst with offset 318, 2017/06/02 23:12:19 in doc user.rst with offset 720, 2017/06/02 23:12:19 Key: requires -> 2017/06/02 23:12:19 in doc user.rst with offset 168, 2017/06/02 23:12:19 Key: section -> 2017/06/02 23:12:19 in doc user.rst with offset 28, 2017/06/02 23:12:19 Key: templates -> 2017/06/02 23:12:19 in doc .gitignore with offset 16, 2017/06/02 23:12:19 Key: documentation -> 2017/06/02 23:12:19 in doc dev.rst with offset 102, 2017/06/02 23:12:19 in doc user.rst with offset 43, 2017/06/02 23:12:19 Key: or -> 2017/06/02 23:12:19 in doc dev.rst with offset 74, 2017/06/02 23:12:19 Key: event -> 2017/06/02 23:12:19 in doc dev.rst with offset 225, 2017/06/02 23:12:19 in doc user.rst with offset 317, 2017/06/02 23:12:19 in doc user.rst with offset 375, 2017/06/02 23:12:19 in doc user.rst with offset 472, 2017/06/02 23:12:19 in doc user.rst with offset 673, 2017/06/02 23:12:19 in doc user.rst with offset 702, 2017/06/02 23:12:19 Key: build -> 2017/06/02 23:12:19 in doc .gitignore with offset 1, 2017/06/02 23:12:19 Key: this -> 2017/06/02 23:12:19 in doc dev.rst with offset 85, 2017/06/02 23:12:19 Key: members -> 2017/06/02 23:12:19 in doc dev.rst with offset 186, 2017/06/02 23:12:19 in doc dev.rst with offset 267, 2017/06/02 23:12:19 in doc dev.rst with offset 285, 2017/06/02 23:12:19 in doc dev.rst with offset 307, 2017/06/02 23:12:19 Key: autofunction -> 2017/06/02 23:12:19 in doc dev.rst with offset 199, 2017/06/02 23:12:19 Key: Alternatively -> 2017/06/02 23:12:19 in doc user.rst with offset 518, 2017/06/02 23:12:19 Key: Use -> 2017/06/02 23:12:19 in doc user.rst with offset 190, 2017/06/02 23:12:19 Key: instance -> 2017/06/02 23:12:19 in doc user.rst with offset 551, 2017/06/02 23:12:19 Key: API -> 2017/06/02 23:12:19 in doc dev.rst with offset 0, 2017/06/02 23:12:19 Key: the -> 2017/06/02 23:12:19 in doc dev.rst with offset 98, 2017/06/02 23:12:19 in doc user.rst with offset 39, 2017/06/02 23:12:19 in doc user.rst with offset 313, 2017/06/02 23:12:19 in doc user.rst with offset 362, 2017/06/02 23:12:19 in doc user.rst with offset 563, 2017/06/02 23:12:19 Key: console -> 2017/06/02 23:12:19 in doc user.rst with offset 230, 2017/06/02 23:12:19 Key: autoclass -> 2017/06/02 23:12:19 in doc dev.rst with offset 148, 2017/06/02 23:12:19 in doc dev.rst with offset 240, 2017/06/02 23:12:19 Key: looking -> 2017/06/02 23:12:19 in doc dev.rst with offset 20, 2017/06/02 23:12:19 Key: provided -> 2017/06/02 23:12:19 in doc user.rst with offset 328, 2017/06/02 23:12:19 Key: If -> 2017/06/02 23:12:19 in doc dev.rst with offset 9, 2017/06/02 23:12:19 Key: 3 -> 2017/06/02 23:12:19 in doc user.rst with offset 184, 2017/06/02 23:12:19 Key: create -> 2017/06/02 23:12:19 in doc user.rst with offset 541, 2017/06/02 23:12:19 Key: manually -> 2017/06/02 23:12:19 in doc user.rst with offset 572, 2017/06/02 23:12:19 Key: an -> 2017/06/02 23:12:19 in doc user.rst with offset 548, 2017/06/02 23:12:19 Key: can -> 2017/06/02 23:12:19 in doc user.rst with offset 537, 2017/06/02 23:12:19 Key: function -> 2017/06/02 23:12:19 in doc dev.rst with offset 58, 2017/06/02 23:12:19 Key: new -> 2017/06/02 23:12:19 in doc dev.rst with offset 221, 2017/06/02 23:12:19 in doc user.rst with offset 669, 2017/06/02 23:12:19 Key: policy -> 2017/06/02 23:12:19 in doc user.rst with offset 386, 2017/06/02 23:12:19 in doc user.rst with offset 483, 2017/06/02 23:12:19 Key: It -> 2017/06/02 23:12:19 in doc user.rst with offset 165, 2017/06/02 23:12:19 Key: from -> 2017/06/02 23:12:19 in doc user.rst with offset 154, 2017/06/02 23:12:19 Key: available -> 2017/06/02 23:12:19 in doc user.rst with offset 144, 2017/06/02 23:12:19 Key: Guide -> 2017/06/02 23:12:19 in doc user.rst with offset 5, 2017/06/02 23:12:19 Key: uvloop -> 2017/06/02 23:12:19 in doc dev.rst with offset 130, 2017/06/02 23:12:19 in doc dev.rst with offset 160, 2017/06/02 23:12:19 in doc dev.rst with offset 214, 2017/06/02 23:12:19 in doc dev.rst with offset 252, 2017/06/02 23:12:19 in doc user.rst with offset 95, 2017/06/02 23:12:19 in doc user.rst with offset 133, 2017/06/02 23:12:19 in doc user.rst with offset 257, 2017/06/02 23:12:19 in doc user.rst with offset 272, 2017/06/02 23:12:19 in doc user.rst with offset 341, 2017/06/02 23:12:19 in doc user.rst with offset 367, 2017/06/02 23:12:19 in doc user.rst with offset 449, 2017/06/02 23:12:19 in doc user.rst with offset 490, 2017/06/02 23:12:19 in doc user.rst with offset 644, 2017/06/02 23:12:19 in doc user.rst with offset 662, 2017/06/02 23:12:19 Key: python -> 2017/06/02 23:12:19 in doc user.rst with offset 411, 2017/06/02 23:12:19 in doc user.rst with offset 606, 2017/06/02 23:12:19 Key: class -> 2017/06/02 23:12:19 in doc dev.rst with offset 68, 2017/06/02 23:12:19 Key: how -> 2017/06/02 23:12:19 in doc user.rst with offset 84, 2017/06/02 23:12:19 Key: it -> 2017/06/02 23:12:19 in doc user.rst with offset 209, 2017/06/02 23:12:19 Key: provides -> 2017/06/02 23:12:19 in doc user.rst with offset 57, 2017/06/02 23:12:19 Key: To -> 2017/06/02 23:12:19 in doc user.rst with offset 293, 2017/06/02 23:12:19 Key: 5 -> 2017/06/02 23:12:19 in doc user.rst with offset 186, 2017/06/02 23:12:19 Key: part -> 2017/06/02 23:12:19 in doc dev.rst with offset 90, 2017/06/02 23:12:19 Key: pip -> 2017/06/02 23:12:19 in doc user.rst with offset 194, 2017/06/02 23:12:19 in doc user.rst with offset 245, 2017/06/02 23:12:19 Key: asyncio -> 2017/06/02 23:12:19 in doc user.rst with offset 301, 2017/06/02 23:12:19 in doc user.rst with offset 430, 2017/06/02 23:12:19 in doc user.rst with offset 460, 2017/06/02 23:12:19 in doc user.rst with offset 625, 2017/06/02 23:12:19 in doc user.rst with offset 690, 2017/06/02 23:12:19 Key: PyPI -> 2017/06/02 23:12:19 in doc user.rst with offset 159, 2017/06/02 23:12:19 Key: static -> 2017/06/02 23:12:19 in doc .gitignore with offset 8, 2017/06/02 23:12:19 Key: specific -> 2017/06/02 23:12:19 in doc dev.rst with offset 49, 2017/06/02 23:12:19 Key: make -> 2017/06/02 23:12:19 in doc user.rst with offset 296, 2017/06/02 23:12:19 Key: Python -> 2017/06/02 23:12:19 in doc user.rst with offset 177, 2017/06/02 23:12:19 Key: code -> 2017/06/02 23:12:19 in doc user.rst with offset 217, 2017/06/02 23:12:19 in doc user.rst with offset 398, 2017/06/02 23:12:19 in doc user.rst with offset 593, 2017/06/02 23:12:19 Key: block -> 2017/06/02 23:12:19 in doc user.rst with offset 222, 2017/06/02 23:12:19 in doc user.rst with offset 403, 2017/06/02 23:12:19 in doc user.rst with offset 598, 2017/06/02 23:12:19 Key: you -> 2017/06/02 23:12:19 in doc dev.rst with offset 12, 2017/06/02 23:12:19 in doc dev.rst with offset 123, 2017/06/02 23:12:19 in doc user.rst with offset 350, 2017/06/02 23:12:19 in doc user.rst with offset 533, 2017/06/02 23:12:19 Key: EventLoopPolicy -> 2017/06/02 23:12:19 in doc dev.rst with offset 167, 2017/06/02 23:12:19 in doc user.rst with offset 497, 2017/06/02 23:12:19 Key: to -> 2017/06/02 23:12:19 in doc user.rst with offset 88, 2017/06/02 23:12:19 in doc user.rst with offset 198, 2017/06/02 23:12:19 Key: This -> 2017/06/02 23:12:19 in doc user.rst with offset 23, 2017/06/02 23:12:19 Key: on -> 2017/06/02 23:12:19 in doc dev.rst with offset 44, 2017/06/02 23:12:19 Key: import -> 2017/06/02 23:12:19 in doc user.rst with offset 423, 2017/06/02 23:12:19 in doc user.rst with offset 442, 2017/06/02 23:12:19 in doc user.rst with offset 618, 2017/06/02 23:12:19 in doc user.rst with offset 637, 2017/06/02 23:12:19 Key: install -> 2017/06/02 23:12:19 in doc user.rst with offset 201, 2017/06/02 23:12:19 in doc user.rst with offset 249, 2017/06/02 23:12:19 in doc user.rst with offset 354, 2017/06/02 23:12:19 Key: Loop -> 2017/06/02 23:12:19 in doc dev.rst with offset 259, 2017/06/02 23:12:19 Key: information -> 2017/06/02 23:12:19 in doc dev.rst with offset 32, 2017/06/02 23:12:19 in doc user.rst with offset 66, 2017/06/02 23:12:19 looping done 2017/06/02 23:12:19 ========================= Search Engine ================= 2017/06/02 23:12:19 searing [bigbang]... 2017/06/02 23:12:19 in file: dev.rst 2017/06/02 23:12:19 in file: user.rst 2017/06/02 23:12:19 done.
TODO:
- 使用B樹替代雜湊表做倒排索引
- 使用檔案持久化倒排索引