符串搜索(查找)概述

字符串查找也叫字符串搜索或字符串匹配，就是从一段文本中查找一小段文本，返回完整匹配的位置。字符串查找的算法有很多种，如：Boyer-Moore算法、Rabin-Karp算法、KMP算法等。最好理解的是朴素搜索法，也就是穷举比较，其算法复杂度接近于：O(N * M)。这里以朴素搜索为例来引入门。

步骤是：

1. 建立两个循环，外循环是被查找的文本，内循环是查找字符串；

2. 将查找字符串逐个与被查找的文本对比，当遇到有不相等时，跳出内循环，文本指针向后移动一位，从下一个开始比较；

如果内循环遍历完成后，还没有不相等的情况，则表示匹配成功，返回当时文本内容的下标，否则返回-1。

朴素算法执行过程分析：

朴素搜索算法代码实现：

function find(str, content) {

var i, conetentLen=content.length

var j, strLen=str.length

// 两个循环，外层是被查找文本，内循环是查找字符串

for (i=0; i < conetentLen; i++) {

for (j=0; j < strLen; j++) {

// 当遇到不有不相等时，跳出从文本下一个字符开始比较

if (str[j] !==content[i + j]) {

break

}

}

// 如果查找字符串全部比较完成表示成功匹配

if (j===strLen) {

return i

}

}

// 如果文本全部比较完还是没有查找到，则返回-1

return -1

}

find('ABC', 'ABABC') // 2

find('AAB', 'AAABC') // 1

find('ABC', 'AABAC') // -1

句话介绍

Web端最快且最具内存灵活性的全文搜索库，零依赖性。

Github地址：https://github.com/nextapps-de/flexsearch

中文翻译介绍

在原始搜索速度方面，FlexSearch优于每一个搜索库，并提供灵活的搜索功能，如多字段搜索，语音转换或部分匹配。 根据使用的选项，它还提供最高内存效率的索引。 FlexSearch引入了一种新的评分算法，称为“上下文索引”，基于预先评分的词典字典体系结构，与其他库相比，实际执行的查询速度提高了1,000,000倍。 FlexSearch还为您提供非阻塞异步处理模型以及Web工作者，以通过专用平衡线程并行地对索引执行任何更新或查询。

安装

可以到官网下载经过压缩的js文件或者使用cdn，也可以使用npm安装

//使用最新版:
<script src="https://cdn.jsdelivr.net/gh/nextapps-de/flexsearch@master/dist/flexsearch.min.js"></script>
//或者特定版
<script src="https://cdn.jsdelivr.net/gh/nextapps-de/flexsearch@0.3.51/dist/flexsearch.min.js"></script>

• npm安装

npm install flexsearch

用法

• 创建一个索引

var index=new FlexSearch();
//或者
var index=FlexSearch.create();
//或者给定一个默认值
var index=new FlexSearch("speed");
//自定义配置
var index=new FlexSearch({
 // default values:
 encode: "balance",
 tokenize: "forward",
 threshold: 0,
 async: false,
 worker: false,
 cache: false
});
//在或者
var index=new FlexSearch("memory", {
 encode: "balance",
 tokenize: "forward",
 threshold: 0
});

• 将文本添加到索引

Index.add(id, string)

index.add(10025, "John Doe");

• 搜索

Index.search(string | options, <limit>, <callback>)

index.search("John");

• 限制数量

index.search("John", 10);

• 异步搜索

//基于回调函数
index.search("John", function(result){
 
 // array of results
});
//基于Promise
index.search("John").then(function(result){
 
 // array of results
});
//es6写法
async function search(query){
 const result=await index.search(query);
 
 // ...
}

• 自定义搜索

index.search({
 query: "John",
 limit: 1000,
 threshold: 5, // >=threshold
 depth: 3, // <=depth
 callback: function(results){
 // ...
 }
});
//或者
index.search("John", {
 limit: 1000,
 threshold: 5,
 depth: 3
 
}, function(results){
 
 // ....
});

• 分页

var response=index.search("John Doe", {
 limit: 5,
 page: true
});
index.search("John Doe", {
 limit: 10,
 page: response.next
});//下一页

• 建议

获取查询建议

index.search({
 query: "John Doe",
 suggest: true
});

启用建议后，将填写所有结果（直到限制，默认为1000），并按相关性排序相似的匹配。

• 更新

Index.update(id, string)

index.update(10025, "Road Runner");

• 移除

Index.remove(id)

index.remove(10025);

• 重置索引

index.clear();

• 销毁

index.destroy();

• 重新初始化

Index.init(<options>)

//使用相同配置重新初始化
index.init();
//使用新的配置重新初始化
index.init({
 /* options */
});
//重新初始化会销毁旧的索引

• 获取长度

var length=index.length;

• 获取寄存器

var index=index.index;

寄存器的格式为“@”+ id

请不要手动修改寄存器，用作只读即可

• 添加自定义匹配器

FlexSearch.registerMatcher({REGEX: REPLACE})

• 为所有实例添加全局匹配：

FlexSearch.registerMatcher({
 '?': 'a', // replaces all '?' to 'a'
 'ó': 'o',
 '[?úù]': 'u' // replaces multiple
});

• 为特定实例添加私有匹配：

index.addMatcher({
 '?': 'a', // replaces all '?' to 'a'
 'ó': 'o',
 '[?úù]': 'u' // replaces multiple
});

• 添加定制编码

通过在索引创建/初始化期间传递函数来分配自定义编码

var index=new FlexSearch({
 encode: function(str){
 
 // do something with str ...
 
 return str;
 }
});

编码器函数获取一个字符串作为参数，返回修改后的字符串

直接调用自定义编码器：

var encoded=index.encode("sample text");

• 注册全局编码

FlexSearch.registerEncoder(name, encoder)

所有实例都可以共享/使用全局编码

FlexSearch.registerEncoder("whitespace", function(str){
 return str.replace(/\s/g, "");
});

初始化索引并分配全局编码

var index=new FlexSearch({ encode: "whitespace" });

直接调用全局编码

var encoded=FlexSearch.encode("whitespace", "sample text");

• 混合/扩展多个编码

FlexSearch.registerEncoder('mixed', function(str){
 
 str=this.encode("icase", str); // built-in
 str=this.encode("whitespace", str); // custom
 
 // do something additional with str ...
 
 return str;
});

• 添加自定义标记

在创建/初始化期间定义私有自定义标记

var index=new FlexSearch({
 tokenize: function(str){
 return str.split(/\s-\//g);
 }
});

• 添加特定于语言的词干分析器和/或过滤器

Stemmer: several linguistic mutations of the same word (e.g. "run" and "running")

Filter: a blacklist of words to be filtered out from indexing at all (e.g. "and", "to" or "be")

在创建/初始化期间分配私有自定义词干分析器或过滤器

var index=new FlexSearch({
 stemmer: {
 
 // object {key: replacement}
 "ational": "ate",
 "tional": "tion",
 "enci": "ence",
 "ing": ""
 },
 filter: [ 
 
 // array blacklist
 "in",
 "into",
 "is",
 "isn't",
 "it",
 "it's"
 ]
});

使用自定义词干分析器

var index=new FlexSearch({
 stemmer: function(value){
 // apply some replacements
 // ...
 
 return value;
 }
});

使用自定义过滤器

var index=new FlexSearch({
 filter: function(value){
 
 // just add values with length > 1 to the index
 
 return value.length > 1;
 }
});

或者将词干分析器/过滤器全局分配给一种语言

Stemmer作为对象（键值对）传递，过滤为数组

FlexSearch.registerLanguage("us", {
 stemmer: { /* ... */ },
 filter: [ /* ... */ ]
});

或者使用一些预定义的词干分析器或首选语言的过滤器

<html>
<head>
 <script src="js/flexsearch.min.js"></script>
 <script src="js/lang/en.min.js"></script>
 <script src="js/lang/de.min.js"></script>
</head>
...

现在您可以在创建/初始化期间分配内置词干分析器

var index_en=new FlexSearch({
 stemmer: "en", 
 filter: "en" 
});
var index_de=new FlexSearch({
 stemmer: "de",
 filter: [ /* custom */ ]
});

在Node.js中，只需要语言包文件即可使用它们

require("flexsearch.js");
require("lang/en.js");
require("lang/de.js");

总结

本文知识大致翻译了部分使用方法，更加强大和完整的用法参考官方Github文档，里面有更加详细的用法！