下面是基于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/

作者：小成Charles

商业工作，学习交流请添加Vx：Lcc-Triumph

原创作品

转载请标注原创文章地址：https://blog.csdn.net/weixin_42999453/article/details/115711676
Github代码下载地址：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

给定一定数量的关键字，对任一篇文本，寻找文本中包含哪些关键字
例如关键字集合如下：


而待检测的文本如下：


当前算法的目的就是从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

http://en.wikipedia.org/wiki/Aho–Corasick_string_matching_algorithm

Aho–Corasick算法

http://multifast.sourceforge.net/

开源实现