精华内容
下载资源
问答
  • 关键字匹配算法
    千次阅读
    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/
    更多相关内容
  • 文本中关键字匹配算法的实现 文本中关键字匹配算法的实现 文本中关键字匹配算法的实现 文本中关键字匹配算法的实现
  • 下面是C语言字符串关键字匹配算法讲解笔记 一、主函数 这段代码块定义了一个全局变量pattern作为目标关键词,其中'\0'是字符串的结束标志。charline是从getline获取到的被匹配句子,while循环条件会一直进行字符...

    作者:小成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

    展开全文
  • :基于多关键字匹配的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









    展开全文
  • 经典的WM算法的源代码,原先就在csdn上下载的,但是不支持中文,而且不支持文件操作。经过改进之后,可以完美的支持中英文混合的多模式匹配,而且支持从文件中读取样本数据以及模式数据,经过测试相当的快。4MB的...
  • 关键字匹配算法

    千次阅读 2015-05-11 10:20:02
    http://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+pyahocorasick,匹配关键字关键字大概在10-20个汉字之间。构建ahocorasick的文本,是从本地文件key_word的读入。格式如下:母婴专区面条,细面,粗面,手工面,蔬菜面,营养面,碎面,挂面,面仔匹配结果...
  • java关键字匹配

    千次阅读 2019-03-25 14:13:27
    java关键字匹配 /** * 关键字匹配 * @param word * @param key * @return */ public boolean compileKeyWord(String word, String keyWord) { Pattern pn = Pattern.comp...
  • 关键字过滤多模式匹配算法(支持中文),支持从文件中读取样本数据以及字典数据,文件附带中英文测试文件和中英文关键字字典可供测试,亲测效率还行
  • 还有因为,之前遇到一个问题,没有办法解决,我来了一招反向匹配,骚的我自己都受不了。然而,身为一个代码猴,我不应该这样不求甚解。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:08
    0.关键词提取 定义:从文本中把与这篇文章意义最相关的一些词语抽取出来。 应用:在文献检索、自动文摘、文本聚类/分类等方面有着重要的应用,它不仅是进行这些工作不可或...关键词提取:针对新文档,通过算法分析...
  • 此时,首先通过关键词自动匹配日志,再检查匹配到的日志的方式可以减少一定工作量。批处理方式进行关键词分类文件在Windows操作系统上,批处理程序不需要安装任何脚本,不需要通过命令等调用,直接双击就可自动处理...
  • 全面综述了应用于入侵检测系统的经典的模式匹配算法,包括单模式匹配算法中的KMP算法、BM算法、RK算法和多模式匹配算法中的AC算法、AC—BM算法,并对各种算法的执行效率进行了总结。通过分析算法的思想,提出了未来...
  • 针对大规模URL关键字的多模匹配算法的性能优化.pdf
  • 接着,对子块提取ORB关键字并计算匹配描述子得到粗匹配点对,采用金字塔光流法追踪ORB特征点,求解特征点的运动位移矢量,以此剔除粗匹配部分错误的匹配对;最后,采用随机采样一致算法进一步剔除冗余匹配点,获取更为精准...
  • 而且,串匹配是这些应用中最耗时的核心问题,好的串匹配算法能显著地提高应用的效率。因此,研究并设计快速的串匹配算法具有重要的理论价值和实际意义。 串匹配问题实际上就是一种模式匹配问题,即在给定的文本串中...
  • 关键字过滤算法

    2013-08-27 17:34:38
    文档描写的是一个关于关键字过滤的算法,跟其他过滤算法不同的是该算法是中英文混合过滤算法
  • 提出了一种关键字长度可变、内容可重置的并行模式匹配硬件实现方法,详细论述了用FPGA 设 计实现了这种方法的技术途径,通过一个设计实例仿真分析表明,这种硬件模式匹配技术设计灵活 方便,匹配速度快,资源利用率...
  • 本程序使用ICTCLAS中文分词系统,支持中文分词,同时实现高效率的关键字匹配,使用的分词系统支持用户自定义词典,并支持GBK和UTF-8编码,在Linux系统上运行,同时避免某些因证书引起的问题,适用于个人研究,因商业...
  • 概要 字符串匹配这个功能,是非常常见的功能,比如"Hello"里是否包含"el"? 在 Java 里用的是indexOf函数,其底层...BF即是 Brute Force 缩写,即暴力匹配算法,也称为朴素匹配算法。例如在A字符串中查找B字符串,...
  • 主要介绍了C#获取关键字附近文字算法,实例分析了文字查找算法的原理与实现技巧,具有一定参考借鉴价值,需要的朋友可以参考下
  • 网络安全态势感知中Trie树关键词高速匹配算法研究.pdf
  • 多关键词匹配个人解决方案

    千次阅读 2017-11-05 16:15:52
    本文章是对于多关键词匹配的两种个人解决方案的介绍,只是想记录一下自己的想法而已,不喜勿喷! ^_^ 最简单也是对于我们来说最方便的解决多关键词匹配的方法就是:从数据库中把关键词列表取出,然后对待检索文章...
  • 本论文所研究的模式匹配算法是一种不同于传统的KMP算法和BM算法的前所未有的模式匹配算法——字符串拆分算法。本论文未在任何正式期刊上发表过,可以通过论文查重,大家可以下载拿去修改修改当做自己的毕业设计...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 94,439
精华内容 37,775
关键字:

关键字匹配算法