精华内容
下载资源
问答
  • 分析了IMS中媒体层、控制层和应用认证机制,针对IMS用户漫游时跨域认证造成开销过大问题,在IMS控制层提出了一种跨域信任机制。该机制通过在HSS和S-CSCF中增加信任证书数据库、证书目录、声明发生器和标签提取...
  • 专业课程设计作业,当初花了差不多三个晚上最后终于实现了Edmonds算法并解决该问题,最后还学会了用... 如果对于二分图最大匹配算法不熟悉,可以参考前篇博文:http://www.cnblogs.com/visayafan/archive/201...

      专业课程设计的作业,当初花了差不多三个晚上最后终于实现了Edmonds算法并解决该问题,最后还学会了用Matlab做简单的交互界面,算是到目前为止本人自我感觉写得最成功的程序,以防将来再重装系统导致文件丢失,所以发上来,欢迎大家发邮件交流指正交流.

      如果对于二分图最大匹配算法不熟悉,可以参考前篇博文:http://www.cnblogs.com/visayafan/archive/2012/05/12/2496896.html


    View more documents from visayafan

     

    一共有RecuCal.m LockMap.m BuildMatrix.m Edmonds.m GUI1.m 这几个文件,我把它们合到一块粘上去了,你再把他们分开保存就可以了. 
    其中前三个文件都是为建立邻接矩阵服务的,Edmonds.m是匈牙利算法的主文件,GUI1.m只是调用Edmonds.m做个界面而已。 
    调用关系是GUI1.m调用Edmonds.m; Edmonds.m调用BuildMatrix.m和LockMap.m ;LockMap.m调用RecuCal.m 
    最后运行GUI1.m就ok了 

    #LockMap.m
    function [LMA, LMB] = LockMap(n, m)
    % LOCKMAP - 求解满足条件锁并设置相应的映射
    % 输入参数:n 表槽数,m 表高度数。
    % 输出参数:LMA,LMB 分别为二维矩阵表示自然数到满足条件锁之间的映射。
    global jiA ouB ary A B mm N
    N = n; mm = m;
    jiA=0; ouB=0;
    A=[]; B=[];
    ary = zeros(1, n);
    RecuCal(n);
    LMA=A; LMB=B;
    [lena, n] = size(LMA);
    [lenb, n] =size(LMB);
    if lena>lenb
        temp = LMA; LMA=LMB;LMB=temp;
        temp = lena;lena=lenb;lenb=temp;
    end
    
    
    
    #RecuCal.m
    function RecuCal(n)
    % RECUCAL - 递归函数
    global jiA ouB ary A B mm N
    if n ==1
        for k=1:mm
            % 调用递归函数时要用到的变量所以
            % 设为全局
            ary(1) = k;
            Max = max(ary); Min = min(ary);
            num = 0; neighbor = 0;
            for i=1:N
                num = num + (Max-ary(i))*(ary(i)-Min);
                if (i~=N)
                    neighbor = max(neighbor, abs(ary(i)-ary(i+1)));
                end
            end
            if (neighbor > mm-1.5)&&(num > 0.5)
                if mod(sum(ary), 2)
                    % 奇数,属于 A 类
                    jiA = jiA+1;
                    A(jiA,:) = ary;
                else
                    % 偶数,属于 B 类
                    ouB = ouB+1;
                    B(ouB,:) = ary;
                end
            end
        end
    else
        for k=1:mm
            ary(n) = k;
            RecuCal(n-1);
        end
    end
    
    
    
    #BuildMatrix.m
    function AB = BuildMatrix(LMA, LMB)
    % BUILDMATRIX - 建立邻接矩阵,若 i 与 j 之间可以互开则 AB(i,j)=1,否则为 0。
    AB = [];
    [lena, n] = size(LMA);
    [lenb, n] =size(LMB);
    for i = 1:lena
        for j=1:lenb
            tmp = 0;
            for k=1:n
                tmp = tmp + abs(LMA(i,k)-LMB(j,k));
            end
            if tmp == 1
                AB(i, j)=1;
            end
        end
    end
    
    
    
    
    
    #Edmonds.m
    function str = Edmonds(n, m)
    % EDMONDS - Edmonds 算法寻找完美匹配
    str = [];
    [LMA, LMB] = LockMap(n, m);
    AB = BuildMatrix(LMA, LMB);
    lena = length(LMA);
    lenb = length(LMB);
    if lena==0
        disp('其中一个分组为空,
        无法匹配'); %当 n=m=3 时只有偶数组无奇数组,
        不能完成
        匹配
        return;
    end
    MatA = zeros(1, lena);
    MatB = zeros(1, lenb);
    X = MatA; Y=MatB; Z=Y;
    NumNoMat = 0;
    % 无法匹配的点的个数
    % 最初匹配,只有一个匹配
    j = find(AB(1,:), 1);
    MatA(1)=j; MatB(j)=1;
    while length(find(MatA==0)) ~= 0
        % 存在不匹配的元素
        J = find(MatA==0); i = J(1);
        % 第 i 个元素未被匹配
        init = i; X(i)=0;
        J = find(AB(i,:));
        % J 为所有与 i 相邻结点
        Y(J) = i; j=J(1);
        while ~isempty(find(Y~=Z))
            if MatB(j) ~= 0
                % j 是匹配点
                Z(j) = Y(j);
                i = MatB(j);
                X(i)=j;
                J = find(AB(i,:));
                Y(J)=i;
                J = find(Y);
                JJ = find(Z);
                J = setxor(intersect(J, JJ), J);
                j=J(1);
            else
                % j 不是匹配点
                i = Y(j);
                MatA(i) = j;
                MatB(j) = i;
                while X(i)
                    j = X(i);
                    i = Z(j);
                    MatA(i) = j;
                    MatB(j) = i;
                end
                break;
            end
        end
        % 如果 Y==Z 则表明该点没有与之相应的匹配,即不存在完美匹配,在 MatA 中标
        % 记为-1if isempty(find(Y~=Z, 1))
            NumNoMat = NumNoMat + 1;
            MatA(init) = -1;
        end
        X(1:lena)=0; Y(1:lenb)=0; Z=Y;
    end
    total = 0;
    for i=1:lena
        k = MatA(i);
        if k<=0 continue; end
        % k<=0 时表明匹配不存在
        stra = ''; strb = '';
        for j=1:n
            stra = [stra, num2str(LMA(i, j)), ' '];
            strb = [strb, num2str(LMB(k, j)), ' '];
        end
        str = [str, stra, '------ ', strb, 10];
        total = total + 1;
    end
    str = [str, '匹配个数有:', num2str(total)];
    
    
    
    #GUI1.m
    function varargout = GUI1(varargin)
    gui_Singleton = 1;
    gui_State = struct('gui_Name',
    mfilename, ...
        'gui_Singleton', gui_Singleton, ...
        'gui_OpeningFcn', @GUI1_OpeningFcn, ...
        'gui_OutputFcn', @GUI1_OutputFcn, ...
        'gui_LayoutFcn', [] , ...
        'gui_Callback', []);
    if nargin && ischar(varargin{1})
        gui_State.gui_Callback = str2func(varargin{1});
    end
    if nargout
        [varargout{1:nargout}] = gui_mainfcn(gui_State, varargin{:});
    else
        gui_mainfcn(gui_State, varargin{:});
    end
    % End initialization code - DO NOT EDIT
    % --- Executes just before GUI1 is made visible.
    function GUI1_OpeningFcn(hObject, eventdata, handles, varargin)
    handles.output = hObject;
    guidata(hObject, handles);
    function varargout = GUI1_OutputFcn(hObject, eventdata, handles)
    varargout{1} = handles.output;
    function pushbutton1_Callback(hObject, eventdata, handles)
    a = get(handles.edit1, 'String');
    b = get(handles.edit2, 'String');
    str = Edmonds(str2num(a), str2num(b));
    set(handles.edit4, 'String', str);
    guidata(hObject, handles);
    function edit1_Callback(hObject, eventdata, handles)
    input = str2num(get(hObject, 'String'));
    guidata(hObject, handles);
    function edit1_CreateFcn(hObject, eventdata, handles)
    if ispc && isequal(get(hObject,'BackgroundColor'),
        get(0,'defaultUicontrolBackgroundColor'))
        set(hObject,'BackgroundColor','white');
    end
    function edit2_Callback(hObject, eventdata, handles)
    input = str2num(get(hObject, 'String'));
    guidata(hObject, handles);
    function edit2_CreateFcn(hObject, eventdata, handles)
    if ispc && isequal(get(hObject,'BackgroundColor'),
        get(0,'defaultUicontrolBackgroundColor'))
        set(hObject,'BackgroundColor','white');
    end
    function slider1_Callback(hObject, eventdata, handles)
    function slider1_CreateFcn(hObject, eventdata, handles)
    if isequal(get(hObject,'BackgroundColor'),
        get(0,'defaultUicontrolBackgroundColor'))
        set(hObject,'BackgroundColor',[.9 .9 .9]);
    end
    function text_result_Callback(hObject, eventdata, handles)
    function text_result_CreateFcn(hObject, eventdata, handles)
    if ispc && isequal(get(hObject,'BackgroundColor'),
        get(0,'defaultUicontrolBackgroundColor'))
        set(hObject,'BackgroundColor','white');
    end
    function edit4_Callback(hObject, eventdata, handles)
    function edit4_CreateFcn(hObject, eventdata, handles)
    if ispc && isequal(get(hObject,'BackgroundColor'),
        get(0,'defaultUicontrolBackgroundColor'))
        set(hObject,'BackgroundColor','white');
    end
    function pushbutton2_Callback(hObject, eventdata, handles)
    set(handles.edit4, 'String', '');
    set(handles.edit1, 'String', '');
    set(handles.edit2, 'String', '');

     

    展开全文
  • 匹配算法在搜索问题中的应用 匹配算法在搜索问题中的应用
  • 摘要:介绍一种优化快速模板的匹配算法,可实现目标实时提取、识别和跟踪,并成功应用于红外热成像跟踪技术研究,解决了复杂背景条件下目标跟踪稳定度差技术难点。该算法用Visual C++编写,可方便地移植到其它...
  • 全面综述了应用于入侵检测系统的经典的模式匹配算法,包括单模式匹配算法中的KMP算法、BM算法、RK算法和多模式匹配算法中的AC算法、AC—BM算法,并对各种算法的执行效率进行了总结。通过分析算法的思想,提出了未来...
  • 主要介绍了Java栈的应用之括号匹配算法,结合实例形式分析了Java使用栈实现括号匹配算法的相关原理、操作技巧与注意事项,需要的朋友可以参考下
  • 本文实例讲述了Java栈的应用之括号匹配算法。分享给大家供大家参考,具体如下:1、LeetCode官网美网:https://leetcode.com/中文网:https://leetcode-cn.com/英语不咋地,所以选择此处选择中文网来进行测试。2、...

    本文实例讲述了Java栈的应用之括号匹配算法。分享给大家供大家参考,具体如下:

    1、LeetCode官网

    美网:https://leetcode.com/

    中文网 :https://leetcode-cn.com/

    英语不咋地,所以选择此处选择中文网来进行测试。

    2、LeetCode中获取第20号题目

    (1)搜索20号题目

    (2)查看题目

    4c08ad16a8cc1be69b3616fe9e85c080.png

    (3)根据题目要求,首先在本地编辑器中完善20号题目的代码--使用java提供的Stack类,代码如下:

    class Solution {

    public boolean isValid(String s) {

    Stack stack=new Stack();

    for (int i=0;i

    char c=s.charAt(i);

    if(c=='('||c=='['||c=='{'){

    stack.push(c);

    }else {

    if(stack.isEmpty())

    return false;

    char topChar=stack.pop();

    if(c==')'&&topChar!='(')

    return false;

    if (c==']'&&topChar!='[')

    return false;

    if(c=='}'&&topChar!='{')

    return false;

    }

    }

    return stack.isEmpty();

    }

    }

    (4)将代码提交到LeetCode代码验证是否通过

    7cc146d66784747a8752b0335b01bbec.png

    这样就完成了括号匹配的相关要求,而且是通过Leetcode来完成的,我感觉太酷了~

    下一节我们将继续学习一个关于Leetcode的知识。

    希望本文所述对大家java程序设计有所帮助。

    展开全文
  • AC多模式匹配算法的优化与应用,孙强,辛阳,针对Aho-Corasick(AC)多模式匹配算法使用大的空间复杂度代价换取小的时间复杂度,提出一种改进算法降低AC多模式匹配算法的空间复杂度,
  • 在计算机科学领域,串模式匹配算法一直都是研究焦点之一。在拼写检查、语言翻译、数据压缩、搜索引擎、网络入侵检测、计算机病毒特征码匹配以及DNA序列匹配应用中,都需要进行串匹配。串匹配就是在主串中查找...
  • 基于自动机的中文多模式匹配算法研究及其应用 ...随着计算机网络技术的飞速发展,信息量呈爆炸式增长,如何提高模式匹配算法的心梗成了信息检索、内容过滤等领域研究的热门课题。本文主要介绍自动机在AC算法、AC_BM...

     

    基于自动机的中文多模式匹配算法研究及其应用

    乐红霞1

    1(西南石油大学计算机科学与技术学院 学号:201821000400

    摘要  模式匹配是计算机应用领域重要的研究方向之一,广泛应用于入侵检测、信息搜索,生物科学等方面。随着计算机网络技术的飞速发展,信息量呈爆炸式增长,如何提高模式匹配算法的心梗成了信息检索、内容过滤等领域研究的热门课题。本文主要介绍自动机在AC算法、AC_BM算法上的应用以及AC算法在NLP上的应用。

    关键词 多模式匹配;AC算法、AC_BM算法;

     

    1 概述

    1.1 模式匹配的意义

    随着互联网的广泛应用,计算机网络给人们带来了方便和快捷,但也被其海量信息所淹没。无序、庞大的信息世界和形式多样的链接方式,让人们在查找所需信息时感到无所适从。同时,一些不良信息也严重影响着人们的身心健康。因此,如何能够更准确、更有效地找到自己感兴趣的内容,屏蔽与需求无关的信息或有害信息是很重要的。

    模式匹配算法作为信息检索和内容过滤的核心,也被广泛地应用于搜索引擎、入侵检测系统、计算机病毒检测、内容过滤防火墙等。面对网络上的大量信息,对中文模式匹配算法进行优化是很重要的,这对于中心信息检索和内容过滤等有非常重要的意义。

     

    1.2模式匹配的相关算法

      最早出现的模式匹配算法是单模式匹配算法 BF算法,后来又有Turbo BMsuanfa BM-Horspool-Raita算法、BMI算法、Simon算法、Shift-Or算法、Apostolico算法、KR算法等。不同于单模式匹配算法,多模式匹配算法扫描一遍文本串能识别出多个模式串。于是有一个经典的多模式匹配算法—AC算法。该算法基于自动机,通过状态转移,一次可识别多个模式串。而AC_BM算法对AC算法进行改进,可跳跃式匹配,但其计算安全跳转距离还很保守,平均跳转距离较小。

     

    2 模式匹配的定义

    模式匹配是数据结构中字符串的一种基本运算,给定一个子串,要求在某个字符串中找出与该子串相同的所有子串,这就是模式匹配。

    假设P是给定的子串,T是待查找的字符串,要求从T中找出与P相同的所有子串,这个问题成为模式匹配问题。P称为模式,T称为目标。如果T中存在一个或多个模式为P的子串,就给出该子串在T中的位置,称为匹配成功;否则匹配失败。

     

    2.1 AC算法

    AC算法是为了解决多模式匹配问题换句话说,就是在大字符串S中,看看小字符串s1, s2,...有没有出现该算法匹配之前先对模式串集合构造有限状态自动机,匹配过程中通过状态的转移,扫描一遍文本串,可识别出全部模式串。AC 算法包括预处理阶段和匹配阶段。

    1)预处理

    预处理阶段的主要任务是构造有限状态自动机并计算三个函数:goto(转移函数),failure(失效函数) output(输出函数)。

    ① 构造有限状态自动机

    设模式串集合 K={y1,y2,...yi...yn}。对 K 中的每个模式串 yi,初始状态为 0。从状态 0 出发,逐个取出 yi中的每一个字符;如果从当前状态出发能够找到标注该字符的矢线,则将矢线所指的状态作为当前状态;否则,添加一个新状态,新状态为已有的最大状态加 1,并将新加入的状态作为当前状态,继续对 yi中的下一个字符进行处理。当模式串集合 K 中所有的模式串都处理完毕,再添加一条从状态 0到状态 0 的自反线,表示保持状态 0 的字符集。例如,设模式串集合 K={he,she,his,hers},所建立的有限状态自动机如图 2.1所示。

     

     2.1有限状态自动机

     

    ②  goto函数

    设状态集合U = {0,1,2,…},文本串当前字符为‘a’,则goto函数为一种映射goto(U,a)->U。

    goto 函数计算过程:如果从当前状态出发能够找到标注字符“a”的矢线,则返回矢线所指的状态,否则返回跳转失败状态 fail。

    ③  failure函数

      失效函数 failure 函数用来计算某个字符失配时,应转移的状态。计算过程:

     (i)若某状态的父状态为0,则该状态的失效函数为 0。

      ii m r

    failure(m)=goto(failure(r),a)。

    ④ output 函数

    输出函数 output 函数用来输出已匹配的模式串,计算过程分为两步:

     (i)  在构造有限状态自动机的过程中,每处理完一个模式串,将该模式串加入到当前状态 s 的输出函数中。

     (ii) 在计算 failure 函数过程中,若 failure(s)=s′,则 output(s)=output(s)∪output(s′)。

     

    2)匹配过程

    ①当前状态s 初始化为 0,文本串指针指向文本串的首字符。 

    ②若文本串的当前指针不为空,则取出所指的字“a”;否则匹配过程结束。 

    ③计算s′=goto(s,a)。若 s′≠fail,则 s=s′,向右移动文本串指针 1 位,并计算 output 函数,若 output(s)=NULL,转步骤②;否则,输出 output(s)的值,表示有模式串匹配成功,转步骤②。 

    ④若 s′=fail,调用 failure 函数,即当前状态 s=failure(s′),转步骤③。

    例如:

    (1ASCII h=104s=115e=101i=105r=114,第一层{h,s}Next表:产生2个新状态,状态1,2

     

     

     

    Base表:Base[0]=-103

      Check表:Check[1]=0;Check[2]=0;

     

    2ASCII h=104s=115e=101i=105r=114,模式集第二层{e,h,i}Next表:产生3个新状态,状态3,4,5

     

     

     

     

    Base表:

    1状态:he,hi; Base[1]=-100

    2状态:sh; Base[2]=-113

      Check表:Check[3]=1;Check[4]=1; Check[5]=2;

     

    3ASCII h=104s=115e=101i=105r=114,模式集第三层{e,s,r}Next表:产生3个新状态,状态6,7,8

     

     

     

     

    Base表:

    3状态:her; Base[3]=-112

    4状态:his; Base[4]=-116

    5状态:sheBase[5]=-97

    Check表:Check[3]=3;Check[7]=4; Check[8]=5;

     

    4ASCII h=104s=115e=101i=105r=114,模式集第四层{s}Next表:产生1个新状态,状态9

     

     

     

    Base表:

    6状态:hers; Base[6]=-111

    Check表:Check[9]=6

     

    python代码实现的结果如下:

     

     

    AC算法预处理时需建立有限状态自动机,其时间复杂为 О(m) ,其中m为所有模式串的长度总和;匹配过程中仅需扫描一遍文本串,时间复杂为 О(n) , n为文本串的长度,与模式串的个数及每个模式串的长度无关。

    单模式匹配算法处理多个模式串时需多次扫描文本串。AC 算法通过有限状态自动机,可对所有模式串并行的进行处理,同单模式匹配算法相比,减少了比较的次数,提高了模式串的匹配速度。

     

    2.2 AC_BM算法

    AC 算法匹配过程需逐个扫描文本串的字符,不能进行跳跃式匹配。改进后为AC_BM 算法,描述如下:

    1)预处理

    ①构建有限状态自动机。

    与AC算法不同的是,AC_BM 算法需构造反向有限状态自动机。例如对模式串“amne”和“abcde”,AC 算法和 AC_BM 算法构造的有限状态自动机如下图所示。

    ②计算跳转距离。

    AC_BM 算法跳转距离的计算借鉴了 BM

    算法的好后缀规则和坏字符规则。设最短模式串长度为 m,失配字符为 t,字符 t 在有限状态自动机中的深度为 k。

    i)好后缀规则

    设已匹配的字符串为 S。若在有限状态自动机的 m 深度内存在以字符串 S作为前缀的模式串,则跳转距离为(m-k)个字符;否则,在有限状态自动机的m 深度内查找以字符串 S 的后缀子串作为前缀的模式串:若存在,设其长度为q,则跳转距离为(m-q)个字符;若不存在,则跳转距离为 1 个字符。

    (ii)坏字符规则

    若失配字符 t 在有限状态自动机的 m 深度内未出现,则跳转距离为(m-k+1)个字符;若字符 t 出现在有限状态自动机中的某个模式串中,设其深度为 pk<pm)(如果字符 t 在模式串多处出现,取其深度 p 的最小值),则跳转距离为(p-k)个字符。

    iii)计算跳转距离

    分别利用坏字符规则和好后缀规则计算出跳转距离,取其较大者作为失配字符 t 的跳转距离。

    2)匹配阶段

    ①初始状态 s 0,文本串指针指向文本串的首字符。文本串的第 m 个字符与有限状态自动机的第 1 层节点与对齐。

    ②若文本串的当前指针不为空,则取出所指的字符“a”;否则匹配过程结束。

    ③计算 s′=goto(s,a)。若 s′≠fail,则 s=s′,并向右移动文本串指针 1 位;否则,利用坏字符规则和好后缀规则分别计算跳转距离,并取其较大者作为文本串指针的跳转距离。

    ④计算 output 函数,若 output(s)=NULL,转步骤②;否则,输出 output(s)的值,表示有模式串匹配成功,转步骤②。

    AC_BM 算法的预处理阶段的时间复杂度同 AC 算法。匹配阶段,最坏情况下的时间复杂度为 О(n) ,其中 n 为文本串的长度;最好情况下的时间复杂度为О(n/ m) ,m 为最短模式串的长度。

    AC_BM 算法实现了模式串的跳跃式匹配,使自动机的跳转距离大于 1,时间效率显著提高。

     

    1. AC算法的应用

      AC算法在中文分词、关键词提取、文本反垃圾、敏感词过滤中都有运行,他们的本质都是关键字匹配。

     

    [1] 宋华,戴一奇.一种用于内容过滤和检测的快速多关键词识别算法[J]. 计算机研究与发展,2004,41(6): 940-945 

    [2]  王慧强,杜晔,庞永刚.入侵检测技术研究[J].计算机应用研究.2003,10:90-115

     

     

     

     

     

     

     

     

    转载于:https://www.cnblogs.com/HonsiaBlogs/p/10781510.html

    展开全文
  • Dinic求最大匹配 O(mn)O(m\sqrt n)O(mn​) 二分图最大匹配关键点和关键边 例题:LOJ#6033.... 二分图最大独立集基于最大匹配的O(m)O(m)O(m)构造方法 ...一般图最大匹配(带花树算法) ...

    无增广路 \Longleftrightarrow 最大匹配

    在这里插入图片描述


    同一个点只需增广一次

    在这里插入图片描述
    在这里插入图片描述


    Dinic求最大匹配 O(mn)O(m\sqrt n)

    在这里插入图片描述


    二分图最大匹配关键点和关键边

    在这里插入图片描述
    例题:LOJ#6033. 「雅礼集训 2017 Day2」棋盘游戏

    在这里插入图片描述
    在这里插入图片描述


    二分图最大独立集的基于最大匹配的O(m)O(m)构造方法

    在这里插入图片描述
    在这里插入图片描述


    二分图字典序最小完备匹配:

    在这里插入图片描述
    在这里插入图片描述


    一般图的最大匹配(带花树算法)

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • FKPCA-SIFT算法在图像匹配的应用
  • 一种应用于室内外无缝定位系统的匹配算法,王佳,邓中亮,为了提高室内外无缝定位系统定位精度,提出一种新指纹匹配算法。该算法融合了Euclidian距离、定位结果间关联性、滤波、阀值等
  • 参考理解:https://oi-wiki.org/string/kmp/ ...构造next数组 void get_next(int next_[], char str[]) { int len = strlen(str); next_[0] = 0; for (int i = 1; i <... /*j表示上一个匹配的长度, j
  • 图像特征匹配算法在航拍图像上的应用比较,石波,索春宝,由于飞行器在飞行过程中横滚角和俯仰角会发生小角度的变化,航拍图像会出现较小程度的尺度变化和仿射变化,这就要求对航拍图像进
  • 的应用--模式匹配算法

    千次阅读 2016-07-12 10:23:15
    朴素模式匹配算法,简单来说,就是对主串每个字符作为子串开头,与要匹配字符串进行匹配。对主串做大循环,每个字符开头做T长度小循环,知道匹配成功或全部遍历完成为止。朴素模式匹配中有很多重复...
  • 为提高近似串匹配速度,采用分块方法从匹配串中提取了新q-gram命中特征,结合新特征提出了一种新近似串匹配算法。实验数据表明新算法消耗了少量过滤时间就获得了较高过滤效率,结果显示新算法在各种匹配...
  • 本篇文章是对串的模式匹配算法(普通算法和KMP算法)的应用进行了详细的分析介绍,需要的朋友参考下
  • 图谱和Kuhn-Munkres算法在图匹配的应用研究
  • 模式匹配是数据结构中字符串的...这篇文章介绍了蛮力法在字符串匹配问题中的应用(JAVA)--朴素模式匹配算法,没有基础的读者可以先参考这篇文章。上述的蛮力法求解的思路为:从左到右比较模式和文本中的每一对相应...
  • printf("随机产生5个位置,请输入这五个位值上字母,回答对一个20分\n"); for(w = 1;w ;w ++) { t = rand() % 26 + 1; printf("请输入第%d个字母:",t); scanf("%s",&num[1]); num[0] = StrLength...
  • 对确定性地图匹配算法作了一系列改进:在各节点处选择适当固定参数替代利用神经网络对参数进行自适应调整,简化了车辆是否进入节点区域判断条件,取消了在跟踪模式下确定性值计算,从而使算法在不降低计算...
  • 针对空气中极线几何不再适用于水下双目图像匹配以及尺度不变特征转换(SIFT)算法只能实现稀疏匹配问题...实验结果表明,该算法优于特征匹配SIFT算法,匹配精度有所提高,成功将区域匹配算法应用于水下图像稠密匹配。
  • 模式匹配算法

    2019-03-25 10:30:09
    1、掌握串的存储表示及基本操作; 2、掌握串的两种模式匹配算法:BF和KMP。 3、了解串的应用
  • 本文主要介绍字符串匹配算法在生物信息学中的应用
  • 提出了一种基于特征图像分支点提取加权Hausdorff距离图像匹配算法,并给出了相应权值求解公式.为满足景象匹配导航系统实时性要求,给出了细化处理预处理方法,减少了特征文件冗余度,提高了匹配搜索快速性....
  • KMP算法通常是我们学习字符串匹配算法时遇见的第一个算法,另外还有Rabin-Karp, Sunday算法等. 相对于其他字符串匹配算法, kmp在字符串...首先上KMP字符串匹配算法,关于KMP算法的详细介绍可以参考从头到尾彻底理解KMP...
  • 本文提出了一种基于蜜蜂交配的协作式图像分割算法(CHBMA),以节省计算时间,同时克服了维数的诅咒.CHBMA基于蜜蜂交配算法的维数。基于蜜蜂交配算法(HBMA)和协同学习技术,极大地提高了算法的搜索能力。此外,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,969
精华内容 1,587
关键字:

匹配算法的应用