精华内容
下载资源
问答
  • 文本中关键字匹配算法的实现 文本中关键字匹配算法的实现 文本中关键字匹配算法的实现 文本中关键字匹配算法的实现
  • :基于多关键字匹配的Sun wu算法进行的分析,结合Qs算法的思想,设计了一种改进的多关
  • 下面是基于KWIC 的关键字匹配算法(管道+过滤器模式下实现) 关键部分的管道+过滤器 软件体系下的实现, 在很多的关键字搜索平台都使用了这一 循环移位+排序输出的 关键字匹配算法: 具体需求如下: 1、使用管道-过滤...

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

    展开全文
  • 文本中关键字匹配算法

    万次阅读 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









    展开全文
  • 关键字匹配算法

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

    千次阅读 2013-07-04 10:00:10
    关键字匹配之BF算法
  • java关键字匹配

    千次阅读 2019-03-25 14:13:27
    java关键字匹配 /** * 关键字匹配 * @param word * @param key * @return */ public boolean compileKeyWord(String word, String keyWord) { Pattern pn = Pattern.comp...
  • 本文实例讲述了python通过BF算法实现关键词匹配的方法。分享给大家供大家参考。具体实现方法如下:#!/usr/bin/python# -*- coding: UTF-8# filename BFimport time"""t="this is a big apple,this is a big apple,...
  • 本程序使用ICTCLAS中文分词系统,支持中文分词,同时实现高效率的关键字匹配,使用的分词系统支持用户自定义词典,并支持GBK和UTF-8编码,在Linux系统上运行,同时避免某些因证书引起的问题,适用于个人研究,因商业...
  • 关键字过滤多模式匹配算法(支持中文),支持从文件中读取样本数据以及字典数据,文件附带中英文测试文件和中英文关键字字典可供测试,亲测效率还行
  • 关键字过滤算法

    2013-05-19 16:23:00
    1) 看到这个题目首先想到的是选择一个高效的字符串匹配算法,于是先到KMP算法。但是细想,KMP虽然充分利用了匹配失败部分的比较信息,但是这仅限于一个字符串的匹配。当有很多字符串需要匹配的时候,KMP无法利用已...
  • import ahocorasick A = ahocorasick.Automaton() for idx, key in enumerate('我 经常 在 微信 公众号 码龙社 看 文章'.split()): A.add_word(key, (idx, key)) sentence = '我 爱 在 北京 天安门 下 看 微信 ...
  • php多关键字匹配扩展

    千次阅读 2013-12-02 13:23:56
    扩展使用了wu-manber匹配算法(http://blog.csdn.net/pi9nc/article/details/9124623),可以应用各种场景的关键字匹配、提取、替换等功能(最常见的一个应用是一篇文章中关键字名字加上超链接)。 代码地址:...
  • 中文文本中的关键字提取算法总结

    千次阅读 2019-07-03 15:32:08
    0.关键词提取 定义:从文本中把与这篇文章意义最相关的一些词语抽取出来。 应用:在文献检索、自动文摘、文本聚类/分类等方面有着重要的应用,它不仅是进行这些工作不可或...关键词提取:针对新文档,通过算法分析...
  • 1、类似于搜索引擎的那种关键字排序。 2、并不是做搜索,而是对历史输入记录的一个匹配 + 排序。 3、高亮关键字
  • 有时候项目中需要进行模糊查询,但是要对查询出来的结果进行匹配度排序,比如搜索关键字是“北”,需要把数据库中第一个字是北的排在前面,此时就可以用mysql的INSTR函数。 INSTR(字段名, 字符串) 这个函数返回字符...
  • 关键字 过滤算法 (转)

    2009-09-09 10:30:00
    因为过滤关键字机制到处可见,...#@等,而且个数可变 3、使用谐音或拆字法变换关键字 在实现自己的算法时也有些问题: 4、随着时间推移,关键字列表会越来越大,有些论坛常用的正则表达式N次扫描的方法显得效率很低...
  • stack算法求SLCA 基本思想:先序遍历后序(自底向上)处理所有包含关键字的结点 从小到大遍历k1,k2两个关键字倒排表中的编码,依次入栈,比较相邻编码,编码中不同部分出栈,出栈时判断其是否为真正的SLCA, 若其没有...
  • 我们发现也经过证实,交换式的排序的算法的时间复杂度的下界是O(n*lgn),但是这真的就是我们的排序算法的极限了吗,事实并不是这样的,我们的多关键字的分配式排序--本文的基数排序就是如此却是打破了这样的瓶颈 ...
  • 里面很多注释 没有详细注释,是因为带着关键字,百度很容易搜到解释。  最主要的核心就是定位。虽然不能百分百解决,但是实用性还是有的     maven依赖 &lt;!-- ...
  • 本文原始链接:... 作者:liigo, 2009/10/29 ...    假设有一个基于关键字匹配的文本过滤系统,或类似的系统,需要一个配置文件,用于设定欲过滤的关键字列表。该怎么设计这样一个配置文件呢?又该如何编
  • 这个算法肯定是最低效的,大家有好的建议可以提出来,主要问题是关键字优先级有点麻烦 php: 目前采用正则匹配: foreach ($keyword_arr as $key=>$value) { $pattern = '/\\b(?:'.$value.')\\b/i'; preg...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 78,508
精华内容 31,403
关键字:

关键字匹配算法