当前位置：首页 > news >正文

C#，字符串匹配（模式搜索）有限自动机（Finite Automata）算法的源代码

news 来源：原创 2024/5/10 14:34:34

一、有限状态自动机

图中两个圆圈，也叫节点，用于表示状态，从图中可以看成，它有两个状态，分别叫0和1。从每个节点出发，都会有若干条边。当处于某个状态时，如果输入的字符跟该节点出发的某条边的内容一样，那么就会引起状态的转换。例如，如果当前状态处于0，输入是字符a，那么状态机就会从状态0进入状态1。如果当前状态是1，输入字符是b或a，那么，状态机就会从状态1进入状态0。如果当前所处的状态，没有出去的边可以应对输入的字符，那么状态机便会进入到错误状态。例如，如果当前处于状态0，输入字符是c，那么状态机就会出错，因为从状态0开始，没有哪条边对应的字符是c。

本代码的运行效果：

二、有限状态机用于字符串匹配（模式搜索）

假定要查找的字符串为P=”ABABCABAB”，被查找的文本为T=”ABABDABACDABABCABAB”。一次读入T的一个字符，用S表示当前读入的T的字符，一开始读入一个字符，于是S=a。然后看看，从P开始，连续几个字符所构成的字符串可以成为S的后缀，由于当前S只有一个字符A，于是从P开始，连续1个字符所形成的字符串”A”，可以作为S的后缀。把这个字符串的长度记为k，于是此时k 等于1。继续从T中读入字符，于是S=”AB”，此时，从P开始，连续两个字符所构成的字符串”AB”可以作为S的后缀，于是k = 2。如此反复。

利用有限状态机便可以构造这样的后缀序列。

源代码：

using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
   public static partial class PatternSearch
   {
       /// <summary>
       /// 下一个状态
       /// </summary>
       /// <param name="patternArray"></param>
       /// <param name="M"></param>
       /// <param name="state"></param>
       /// <param name="x"></param>
       /// <returns></returns>
       public static int NextState(char[] patternArray, int M, int state, int x)
       {
           if (state < M && (char)x == patternArray[state])
           {
               return state + 1;
           }

           for (int ns = state; ns > 0; ns--)
           {
               if (patternArray[ns - 1] == (char)x)
               {
int i;
                   for (i = 0; i < ns - 1; i++)
                   {
                       if (patternArray[i] != patternArray[state - ns + 1 + i])
                       {
                           break;
                       }
                   }
                   if (i == ns - 1)
                   {
                       return ns;
                   }
               }
           }

return 0;
}

       /// <summary>
       /// 计算TF表
       /// </summary>
       /// <param name="patternArray"></param>
       /// <param name="M"></param>
       /// <returns></returns>
       public static int[,] Compute_TF(char[] patternArray, int M)
       {
           int[,] TF = new int[M + 1, ALPHA_CODE_MAX];
           for (int state = 0; state <= M; ++state)
           {
               for (int x = 0; x < ALPHA_CODE_MAX; ++x)
               {
                   TF[state, x] = NextState(patternArray, M, state, x);
               }
           }
           return TF;
       }

       /// <summary>
       /// 字符串匹配算法（模式搜索）Finite Automata算法
       /// </summary>
       /// <param name="text"></param>
       /// <param name="pattern"></param>
       /// <returns></returns>
       public static List<int> Finite_Automata_Search(string text, string pattern)
       {
           List<int> matchs = new List<int>();

           int M = pattern.Length;
           int N = text.Length;
           int[,] TF = Compute_TF(pattern.ToCharArray(), M);//, TF);
           int state = 0;
           for (int i = 0; i < N; i++)
           {
               state = TF[state, text[i]];
               if (state == M)
               {
                   matchs.Add((i - M + 1));
               }
           }

           return matchs;
       }
   }
}

-----------------------------------------------------------------------------

POWER BY TRUFFER.CN

using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;namespace Legalsoft.Truffer.Algorithm
{public static partial class PatternSearch{/// <summary>/// 下一个状态/// </summary>/// <param name="patternArray"></param>/// <param name="M"></param>/// <param name="state"></param>/// <param name="x"></param>/// <returns></returns>public static int NextState(char[] patternArray, int M, int state, int x){if (state < M && (char)x == patternArray[state]){return state + 1;}for (int ns = state; ns > 0; ns--){if (patternArray[ns - 1] == (char)x){int i;for (i = 0; i < ns - 1; i++){if (patternArray[i] != patternArray[state - ns + 1 + i]){break;}}if (i == ns - 1){return ns;}}}return 0;}/// <summary>/// 计算TF表/// </summary>/// <param name="patternArray"></param>/// <param name="M"></param>/// <returns></returns>public static int[,] Compute_TF(char[] patternArray, int M){int[,] TF = new int[M + 1, ALPHA_CODE_MAX];for (int state = 0; state <= M; ++state){for (int x = 0; x < ALPHA_CODE_MAX; ++x){TF[state, x] = NextState(patternArray, M, state, x);}}return TF;}/// <summary>/// 字符串匹配算法（模式搜索）Finite Automata算法/// </summary>/// <param name="text"></param>/// <param name="pattern"></param>/// <returns></returns>public static List<int> Finite_Automata_Search(string text, string pattern){List<int> matchs = new List<int>();int M = pattern.Length;int N = text.Length;int[,] TF = Compute_TF(pattern.ToCharArray(), M);//, TF);int state = 0;for (int i = 0; i < N; i++){state = TF[state, text[i]];if (state == M){matchs.Add((i - M + 1));}}return matchs;}}
}