-
2014-05-27 11:29:02
下面是基于KWIC 的关键字匹配算法(管道+过滤器模式下实现)
关键部分的管道+过滤器 软件体系下的实现, 在很多的关键字搜索平台都使用了这一 循环移位+排序输出的 关键字匹配算法:
具体需求如下:
1、使用管道-过滤器风格:
每个过滤器处理数据,然后将结果送至下一个过滤器,。要有数据传入,过滤器即开始工作。过滤器之间的数据共享被严格限制在管道传输
四个过滤器:
输入(Input filter):
从数据源读取输入文件,解析格式,将行写入输出管道
移位(CircularShifter filter):循环移位
排序(Alphabetizer filter):
输出(Output filter)
管道:
in_cs pipe
cs_al pipe
al_ou pile
例如:
代码如下:
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.IO; namespace KWIC { /// <summary> /// 管道类 /// </summary> public class Pipe { List<string> word; public List<string> read() { return word; } public void write(List<string> word) { this.word = word; } } /// <summary> /// 管道之间的过滤器接口 /// </summary> public abstract class Filter { public virtual void Transform() { } } /// <summary> /// 继承并实现实现管道接口 /// </summary> public class InputFilter : Filter { public Pipe outPipe; public List<string> word; public InputFilter(List<string> word, Pipe outPipe) { this.word = word; this.outPipe = outPipe; } public void Transform() { outPipe.write(word); } } /// <summary> /// 继承并实现过滤器接口 /// </summary> public class CircleShiftFilter : Filter { public Pipe inputPipe; public Pipe outPipe; public CircleShiftFilter(Pipe inputPipe, Pipe outPipe) { this.inputPipe = inputPipe; this.outPipe = outPipe; } /// <summary> /// 关键的循环移位函数 /// </summary> public virtual void Transform() { List<string> word = inputPipe.read(); /// 补充代码,将WORD数组中字符串循环移位 List<string> turned_words = new List<string>(); // 获得每一行字符串数据 foreach (string line in word) { // 拆分一句话 string[] words = line.Split(' '); // 获取单词数 ulong word_number = (ulong)words.LongLength; // 临时存储中间排序好的串 List<string> tmp_words = new List<string>(); tmp_words.Clear(); tmp_words.Add(line); string tmp_line = ""; for (ulong i = 0; i < word_number - 1; i++) { // 获取上一行串 tmp_line = tmp_words[tmp_words.Count - 1]; // 获取上一行串的最后一个单词 string last_word = tmp_line.Split(' ')[word_number -1]; // 获取上一行串的除了最后一个单词之外的所有单词 string left_words = tmp_line.Substring(0, (tmp_line.Length -last_word.Length-1 )); tmp_words.Add(last_word +" "+ left_words ); } // 移除原有的串 tmp_words.RemoveAt(0); // 将一句移位的串加到临时的list集合 turned_words.AddRange(tmp_words); } // 将所有移位的串加到原来list集合 word.AddRange(turned_words); / outPipe.write(word); } } /// <summary> /// 实现的排序过滤器类 /// </summary> public class AlphaFilter : Filter { public Pipe inputPipe; public Pipe outPipe; public AlphaFilter(Pipe inputPipe, Pipe outPipe) { this.inputPipe = inputPipe; this.outPipe = outPipe; } /// <summary> /// 排序输出函数 /// </summary> public void Transform() { List<string> word = inputPipe.read(); // 补充代码,将word数组中单词排序输出/ word.Sort(); outPipe.write(word); } } /// <summary> /// 实现输出过滤器接口类 /// </summary> public class OutputFilter : Filter { public Pipe inputPipe; public Pipe outPipe; public OutputFilter(Pipe inputPipe, Pipe outPipe) { this.inputPipe = inputPipe; this.outPipe = outPipe; } public void Transform() { List<string> word = inputPipe.read(); outPipe.write(word); } } /// <summary> /// 程序的整体运行框架 /// </summary> public class KWIC_System { Pipe in_cs; // create three objects of Pipe Pipe cs_al; // and one object of type Pipe al_ou; // FileInputStream Pipe ou_ui; // FileInputStream InputFilter inputFilter; CircleShiftFilter shifter; AlphaFilter alpha; OutputFilter output; // output to screen public KWIC_System() { in_cs = new Pipe(); // create three objects of Pipe cs_al = new Pipe(); // and one object of type al_ou = new Pipe(); // FileInputStream ou_ui = new Pipe(); // FileInputStream List<string> word = new List<string>(); word.Add(Regex.Replace("I love you".Trim(), @"\s+", " ")); //正则会获取到所有类型的空格(比如制表符,新行等等),然后将其替换为一个空格 word.Add(Regex.Replace("me too".Trim(), @"\s+", " ")); word.Add(Regex.Replace("do you know".Trim(), @"\s+", " ")); inputFilter = new InputFilter(word, in_cs); shifter = new CircleShiftFilter(in_cs, cs_al); alpha = new AlphaFilter(cs_al, al_ou); output = new OutputFilter(al_ou,ou_ui); // output to screen } public List<string > GetResult() { inputFilter.Transform(); shifter.Transform(); alpha.Transform(); output.Transform(); return ou_ui.read(); } } }
(备注:如果想换行这里想换行输出,需要在结尾输出的每一行结尾加‘\r\n’)
在广泛的搜索技术中,其实这个关键字匹配算法应用范围很广,比如我们常见的Baidu和Google的搜索关键字 提示功能。
个人论坛:http://itpark.sinaapp.com/更多相关内容 -
文本中关键字匹配算法的实现
2020-02-06 23:30:33文本中关键字匹配算法的实现 文本中关键字匹配算法的实现 文本中关键字匹配算法的实现 文本中关键字匹配算法的实现 -
【c语言笔记】字符串关键字匹配算法
2021-04-14 22:40:24下面是C语言字符串关键字的匹配算法讲解笔记 一、主函数 这段代码块定义了一个全局变量pattern作为目标关键词,其中'\0'是字符串的结束标志。charline是从getline获取到的被匹配句子,while循环条件会一直进行字符...作者:小成Charles
商业工作,学习交流请添加Vx:Lcc-Triumph
原创作品
转载请标注原创文章地址:https://blog.csdn.net/weixin_42999453/article/details/115711676Github代码下载地址:https://github.com/xiaocheng99/c_project
引言
这是一个学习C语言的笔记开篇,做一些简单有趣的c小程序。下面是C语言字符串关键字的匹配算法讲解笔记
一、主函数
这段代码块定义了一个全局变量
pattern
作为目标关键词,其中'\0'
是字符串的结束标志。charline
是从getline
获取到的被匹配句子,while
循环条件会一直进行字符串的输入,直到出现一个完整的句子就会执行strIndex
函数来判断当前句子是否包含关键字,下面来讲解函数getLine
和函数strIndex
#include <stdio.h> #define MAXLINE 1000 char pattern[] = "charles\0"; int main() { char charLine[MAXLINE]; int found = 0; while (getLine(charLine, MAXLINE)>0) { //printf("keypress:%s", charLine); if (strIndex(charLine,pattern)>=0) { printf("\"loud\" postion:%s", charLine); found++; } } return found; }
二、getLine函数
这里其实是进行字符串的输入,当输入为换行时,缓冲区会判断到为换行符
'\n'
,这时候我们就判定为当前为一个句子,跳出循环,返回一个i,此时的i是大于零的,在主函数里面就是一个真值,如果当前为EOF(End Of File)
,即为结束(windows下按Ctrl+Z再回车),此时不返回值,在主函数里面就是假,不执行接下来的程序。int getLine(char line[],int max) { int c, i; i = 0; while (--max > 0 && (c=getchar())!=EOF && c!= '\n') { line[i++] = c; } if (c=='\n') { line[i++] = c; line[i] = '\0'; return i; } }
三、strIndex函数
这里是实现字符串匹配的主要算法逻辑,第一个
for
循环首先对字符串进行遍历,并且第二个for
循环一直在对字符串与关键词的第一个字符进行比较,如果发现字符串的某一个字符和关键词的第一个字符相等,那么第二个for
循环就会执行,去依次判断字符串后面几个和关键词的字符是否相同,由于关键词有一个‘\0’
结束符,当完全匹配的时候,关键词字符串数组下标将会累加到结束符的下标,所以当关键词下标指向的字符为'\0'
时,则找到所匹配的字符串,并且返回一个大于零的下标。主函数收到后,打印当前句子。int strIndex(char source[],char serachfor[]) { int i, j, k; for (i = 0; source[i] != '\0'; i++) { for (j = i, k = 0; serachfor[k] != '\0'&&source[j] == serachfor[k];j++,k++); if (k>0&&serachfor[k]=='\0') { return i; } } return -1; }
Github代码下载地址:https://github.com/xiaocheng99/c_project
作者:小成Charles
商业工作,学习交流请添加Vx:Lcc-Triumph
原创作品
转载请标注原创文章地址:https://blog.csdn.net/weixin_42999453/article/details/115711676 -
一种改进的多关键字匹配算法
2013-03-01 19:44:34:基于多关键字匹配的Sun wu算法进行的分析,结合Qs算法的思想,设计了一种改进的多关 -
文本中关键字匹配算法
2016-06-16 09:33:38这个文本处理需要一个算法, 普通的文本处理直接去遍历所有的关键字,但是这种算法太复杂,时间复杂度太高。 之前的文章中有说过,实际用到的算法,为了加快执行速度,都是在时间和空间上做的兑换。这里同样可以,...
给定一定数量的关键字,对任一篇文本,寻找文本中包含哪些关键字
例如关键字集合如下:
而待检测的文本如下:
当前算法的目的就是从test.txt中快速的检索有没有给定的keyWord.txt中的关键字
具体的代码下载地址是:http://download.csdn.net/detail/sinat_22013331/9551006,这部分代码是用C#写的,如果要java或者其他语言的版本,可以对照着改动一些。
这个文本处理需要一个算法, 普通的文本处理直接去遍历所有的关键字,但是这种算法太复杂,时间复杂度太高。
之前的文章中有说过,实际用到的算法,为了加快执行速度,都是在时间和空间上做的兑换,用存储空间的增加来换取执行时间的减小。
这里同样可以,通过增加存储空间来减少程序执行时间。
可以选择开一个数组,数组的长度是char类型的最大长度加一。
数组的相应字符对应位置上的数值用二进制表示。假设关键字的长度最长为15,则可以用两个字节的数字来表示,也就是一个short类型。
假设数字为 0000 0000 0010 0110, 也就是38。则表示当前这个字符,可能出现在关键字的第2,3,6位上。由此做倒排索引,可以更方便的得到答案。
//对应位上的值存放的是每个字符在对应位数上是否存在敏感词, //比如fastPositionCheck[7] = 38, 也就是0010 0110 表示某个ascll码为7的字符可能出现在关键字的第2,3,6位上 private short[] fastPositionCheck = new short[char.MaxValue + 1];
这个实现方案可以变成:首先创建一个关键字字典,在这个字典中包含所有的关键字。同时在这个字典中提供针对某个字符的快速检验方法,比如说查看当前关键字是否出现在第一位。
创建的字典如下:
//存放所有关键词 private HashSet<string>[] words = new HashSet<string>[ char.MaxValue + 1 ];
字典中的快速检验方法,这里提供两种,分别是验证某字符是否会出现在关键字的第几位上,以及当前字符时候是某关键字的第一位,如下:
//对应位上的值存放的是每个字符在对应位数上是否存在敏感词, //比如fastPositionCheck[7] = 35, 也就是0010 0011 表示某个ascll码为7的字符可能出现在关键字的第1,2,6位上 private short[] fastPositionCheck = new short[char.MaxValue + 1]; //存放以某个字符为第一位的关键词的长度 private short[] fastLengthCheck = new short[char.MaxValue + 1];
于是字典建立完成之后,就要将所有的关键字添加到字典中,在添加的时候,对各种存储空间赋值。操作如下:/// <summary> /// 向字典中添加关键词 /// </summary> /// <param name="word"></param> /// <returns></returns> public bool AddWord( string word ) { bool result = false; try { maxStoreWordLength = Math.Max(maxStoreWordLength, word.Length); minStoreWordLength = Math.Min(minStoreWordLength, word.Length); //这些运算符的运用简直了,神来之笔 for (int i = 0; i < word.Length; i++) { fastPositionCheck[word[i]] |= (short)(1 << i); } //记录以某个字开头的关键字的长度信息,左移位数长度为该字符串长度减一 fastLengthCheck[word[0]] |= (short)(1 << (word.Length - 1)); if (words[word[0]] == null) { words[word[0]] = new HashSet<string>(); } if (!words[word[0]].Contains(word)) { words[word[0]].Add(word); } result = true; } catch (Exception e) { Console.WriteLine(e.Message); } return result; } }
到这里,一个完整的字典就建立完成了,下面来说字典的使用。
在字典的使用中,前面已经讲过KMP算法了,这里的思路有点像,还是从string的第一个字符开始,逐渐向后遍历,直到最后一个字符。遍历的时候作快速判定,此时的判定依据就是前面提到的几个数组。具体代码如下:
public void CheckNormalWord(string text ) { int index = 0; while (index < text.Length) { //首先判断当前字符是否是某关键字的第一个字符,不是时就继续向下遍历 if ((keywordDict.FastCheck[text[index]] & 1) == 0) { do { index++; } while ( (index < text.Length) && ((keywordDict.FastCheck[text[index]] & 1) == 0) ); if (index >= text.Length) { break; } } //此时已经判定,当前的这个字符会出现在关键词的第一位上 //在判断 char begin = text[index]; int jump = 1; for (int j = 0; j <= Math.Min(keywordDict.MaxWordLength, text.Length - index - 1); j++) { char current = text[index + j]; //判断当前字符是否会出现在关键字的对应位上,实现快速判断 if ((keywordDict.FastCheck[current] & (1 << Math.Min(j, keywordDict.MaxWordLength))) == 0) { break; } //当判决的长度大于关键字的最小长度时,当前的截取字符串有可能会是关键字,要做详细判定 if (j + 1 >= keywordDict.MinWordLength) { if ((keywordDict.FastLength[begin] & (1 << Math.Min(j, keywordDict.MaxWordLength))) > 0) { string sub = text.Substring(index, j + 1); //在字典中搜索判断,得出结论。同时给出跳转位数,供下一次跳转用 if (keywordDict.Words[begin] != null && keywordDict.Words[begin].ContainsKey(sub)) { jump = sub.Length; Console.WriteLine(sub); } } } } index += jump; } }
这样就实现了整个文本中搜索指定关键字的算法。具体的代码详见 https://github.com/BLYang7/HighlightKeyword
-
多模式匹配算法(支持中文多关键字匹配)
2013-01-14 20:21:18经典的WM算法的源代码,原先就在csdn上下载的,但是不支持中文,而且不支持文件操作。经过改进之后,可以完美的支持中英文混合的多模式匹配,而且支持从文件中读取样本数据以及模式数据,经过测试相当的快。4MB的... -
多关键字匹配算法
2015-05-11 10:20:02http://en.wikipedia.org/wiki/Aho–Corasick_string_matching_algorithm Aho–Corasick算法 http://multifast.sourceforge.net/ 开源实现
http://en.wikipedia.org/wiki/Aho–Corasick_string_matching_algorithm
Aho–Corasick算法
http://multifast.sourceforge.net/
开源实现 -
简单关键词匹配算法
2021-02-25 19:34:39针对微博的短篇博文,编写的简单分词和匹配算法。相对于一篇文档的复杂分词算法,能够在效率和可用性上得到较好的平衡。package com.sina.tblog.sentiment;import java.io.BufferedReader;import java.io.File;... -
算法 - python ahocorasick 从本地文件读取文本,进行关键字匹配,匹配失败
2020-12-10 06:22:39问 题使用Python+pyahocorasick,匹配关键字,关键字大概在10-20个汉字之间。构建ahocorasick的文本,是从本地文件key_word的读入。格式如下:母婴专区面条,细面,粗面,手工面,蔬菜面,营养面,碎面,挂面,面仔匹配结果... -
java关键字匹配
2019-03-25 14:13:27java关键字匹配 /** * 关键字匹配 * @param word * @param key * @return */ public boolean compileKeyWord(String word, String keyWord) { Pattern pn = Pattern.comp... -
关键字过滤多模式匹配算法(支持中文)
2017-11-07 15:49:30关键字过滤多模式匹配算法(支持中文),支持从文件中读取样本数据以及字典数据,文件附带中英文测试文件和中英文关键字字典可供测试,亲测效率还行 -
Java----用正则表达式匹配Java源码中的关键字
2021-02-12 20:11:07还有因为,之前遇到一个问题,没有办法解决,我来了一招反向匹配,骚的我自己都受不了。然而,身为一个代码猴,我不应该这样不求甚解。Java中不可能没有,我要的方法。(如果没有,我立马转学Cshit去。)扯淡结束,先... -
3种经典查找算法(Java)
2021-04-22 18:09:55/*** 二分查找** @param arr 数组* @param key 待查找关键字* @return 返回折半下标, -1表示不存在该关键字*/public static int binarySearch(int[] arr, int key) {int left = 0, right = arr.length - 1, mid;... -
关键词敏感字高效查找匹配算法
2019-01-04 15:21:30本算法对纯文本匹配执行效率已改进到:5000字5毫秒(2400敏感词库) 原理:基于多叉树的查找。 import java.util.HashMap; import java.util.HashSet; import java.util.Iterator; import java.util.List; import... -
中文文本中的关键字提取算法总结
2019-07-03 15:32:080.关键词提取 定义:从文本中把与这篇文章意义最相关的一些词语抽取出来。 应用:在文献检索、自动文摘、文本聚类/分类等方面有着重要的应用,它不仅是进行这些工作不可或...关键词提取:针对新文档,通过算法分析... -
Python脚本:通过关键词匹配日志
2021-01-29 10:12:08此时,首先通过关键词自动匹配日志,再检查匹配到的日志的方式可以减少一定工作量。批处理方式进行关键词分类文件在Windows操作系统上,批处理程序不需要安装任何脚本,不需要通过命令等调用,直接双击就可自动处理... -
模式匹配算法在入侵检测中的应用
2020-07-30 03:23:19全面综述了应用于入侵检测系统的经典的模式匹配算法,包括单模式匹配算法中的KMP算法、BM算法、RK算法和多模式匹配算法中的AC算法、AC—BM算法,并对各种算法的执行效率进行了总结。通过分析算法的思想,提出了未来... -
针对大规模URL关键字的多模匹配算法的性能优化.pdf
2022-07-12 09:25:07针对大规模URL关键字的多模匹配算法的性能优化.pdf -
基于改进ORB的图像特征匹配算法研究
2021-02-11 23:23:05接着,对子块提取ORB关键字并计算匹配描述子得到粗匹配点对,采用金字塔光流法追踪ORB特征点,求解特征点的运动位移矢量,以此剔除粗匹配部分错误的匹配对;最后,采用随机采样一致算法进一步剔除冗余匹配点,获取更为精准... -
KMP串匹配算法,并行计算
2020-05-06 11:21:19而且,串匹配是这些应用中最耗时的核心问题,好的串匹配算法能显著地提高应用的效率。因此,研究并设计快速的串匹配算法具有重要的理论价值和实际意义。 串匹配问题实际上就是一种模式匹配问题,即在给定的文本串中... -
关键字过滤算法
2013-08-27 17:34:38文档描写的是一个关于关键字过滤的算法,跟其他过滤算法不同的是该算法是中英文混合过滤算法 -
入侵检测中模式匹配算法的FPGA实现
2011-05-05 19:15:57提出了一种关键字长度可变、内容可重置的并行模式匹配硬件实现方法,详细论述了用FPGA 设 计实现了这种方法的技术途径,通过一个设计实例仿真分析表明,这种硬件模式匹配技术设计灵活 方便,匹配速度快,资源利用率... -
ICTCLAS中文分词和关键字匹配
2015-12-25 14:09:24本程序使用ICTCLAS中文分词系统,支持中文分词,同时实现高效率的关键字匹配,使用的分词系统支持用户自定义词典,并支持GBK和UTF-8编码,在Linux系统上运行,同时避免某些因证书引起的问题,适用于个人研究,因商业... -
数据结构与算法--字符串匹配算法
2022-04-06 15:25:56概要 字符串匹配这个功能,是非常常见的功能,比如"Hello"里是否包含"el"? 在 Java 里用的是indexOf函数,其底层...BF即是 Brute Force 缩写,即暴力匹配算法,也称为朴素匹配算法。例如在A字符串中查找B字符串,... -
C#获取关键字附近文字算法实例
2020-09-03 12:48:42主要介绍了C#获取关键字附近文字算法,实例分析了文字查找算法的原理与实现技巧,具有一定参考借鉴价值,需要的朋友可以参考下 -
网络安全态势感知中Trie树关键词高速匹配算法研究.pdf
2021-09-20 00:45:13网络安全态势感知中Trie树关键词高速匹配算法研究.pdf -
多关键词匹配个人解决方案
2017-11-05 16:15:52本文章是对于多关键词匹配的两种个人解决方案的介绍,只是想记录一下自己的想法而已,不喜勿喷! ^_^ 最简单也是对于我们来说最方便的解决多关键词匹配的方法就是:从数据库中把关键词列表取出,然后对待检索文章... -
一种新的模式匹配(模糊搜索)算法
2018-09-24 10:54:24本论文所研究的模式匹配算法是一种不同于传统的KMP算法和BM算法的前所未有的模式匹配算法——字符串拆分算法。本论文未在任何正式期刊上发表过,可以通过论文查重,大家可以下载拿去修改修改当做自己的毕业设计...