Boyer-Moore快速查找算法

小蜗牛

文本快速查找算法,可以不区分大小写~
适用于,查找大文本...或者,输入一个值,查找多个目标...

如果是很短的文本,并且频繁切换要查找的子文本(也就是每一次查找都初始化),不会更快,只会更慢,请熟知!


<火山程序 类型 = "通常" 版本 = 1 />

类 BM查找算法 <注释 = "Boyer-Moore算法" 注释 = "" 注释 = "https://cloud.tencent.com/developer/article/1490414" 折叠>
{
    变量 m_短文本 <类型 = 文本型>
    变量 m_短文本表 <类型 = 整数数组类>
    变量 m_短文本长度 <类型 = 整数>
    变量 m_区分大小写 <类型 = 逻辑型>

    方法 计算字符表 <静态 注释 = "computeBadCharTable" 折叠>
    参数 要计算的文本 <类型 = 文本型>
    参数 返回表 <类型 = 整数数组类>
    {
        变量 i <类型 = 整数>
        变量 当前字符 <类型 = 字符>
        返回表.重置数组 (数值范围.最大字符值 + 1, 假)
        循环 (0, 返回表.取成员数 (), i)
        {
            返回表.置成员值 (i, -1)
        }
        循环 (0, 取文本长度 (要计算的文本), i)
        {
            当前字符 = 取字符 (要计算的文本, i)
            返回表.置成员值 (当前字符, i)
        }
    }

    方法 初始化 <公开 注释 = "一般只需要初始化一次即可" 折叠>
    参数 要查找的子文本 <类型 = 文本型 注释 = "要查找的子文本!~">
    参数 区分大小写 <类型 = 逻辑型>
    {
        m_短文本 = 要查找的子文本
        m_短文本长度 = 取文本长度 (m_短文本)
        m_区分大小写 = 区分大小写
        如果 (m_区分大小写 == 假)
        {
            自身到大写 (m_短文本)
        }
        计算字符表 (m_短文本, m_短文本表)
    }

    方法 查找 <公开 类型 = 整数 注释 = "可以多次查找~">
    参数 长文本指针 <类型 = 变整数 注释 = "UTF-16文本指针">
    参数 长文本长度 <类型 = 整数 注释 = "要查找的长度~">
    {
        变量 短文本索引 <类型 = 整数>
        变量 起始位置 <类型 = 整数>
        变量 短文本地址 <类型 = 变整数>
        变量 短文本表指针 <类型 = 变整数 注释 = "数组地址">
        变量 x <类型 = 整数>
        变量 ""
        变量 j <类型 = 整数>
        变量 i <类型 = 整数>
        变量 max <类型 = 整数>
        变量 区分大小写 <类型 = 逻辑型>
        短文本索引 = m_短文本长度 - 1
        短文本地址 = 取文本指针 (m_短文本)
        短文本表指针 = m_短文本表.取数组指针 ()

        x = 长文本长度 - 短文本索引
        区分大小写 = m_区分大小写

        判断循环 (起始位置 <= x)
        {
            j = 短文本索引
            i = 起始位置 + j
            如果 (区分大小写)
            {
                判断循环 (j >= 0 && 文本指针_取字符 (短文本地址, j) == 文本指针_取字符 (长文本指针, i))
                {
                    j = j - 1
                    i = i - 1
                }
            }
            否则
            {
                判断循环 (j >= 0 && 文本指针_取字符 (短文本地址, j) == 字符_到大写 (文本指针_取字符 (长文本指针, i)))
                {
                    j = j - 1
                    i = i - 1
                }
            }

            如果 (j < 0)
            {
                返回 (起始位置)  // 找到匹配
            }
            否则
            {
                // 坏字符规则
                max = j - 读指针处值 (短文本表指针 + 文本指针_取字符 (长文本指针, i) * 4, 整数)  // 读指针处对象 (短文本表指针, 整数数组类).取成员 (文本指针_取字符 (长文本指针, i))
                如果 (max < 1)
                {
                    max = 1
                }
                起始位置 = 起始位置 + max
            }
        }

        返回 (-1)  // 未找到匹配
    }

    方法 文本指针_取字符 <静态 类型 = 字符 折叠 @嵌入式方法 = "">
    参数 文本指针 <类型 = 变整数>
    参数 索引 <类型 = 整数 注释 = "请确保不会越界~">
    {
        @ *(wchar_t*)(@<文本指针> + @<索引> * 2)

        // 返回 (读指针处值 (文本指针 + 索引 + 索引, 字符))
    }

    方法 字符_到大写 <静态 类型 = 字符 折叠 @视窗.前缀文本 = "inline">
    参数 当前字符 <类型 = 字符>
    {
        如果 (当前字符 >= 'a' && 当前字符 <= 'z')
        {
            当前字符 = 当前字符 - (字符)' '
        }
        返回 (当前字符)
    }
}

aycap

要多长的文本才算大文本?

小蜗牛

aycap 发表于 2024-3-14 09:07
要多长的文本才算大文本?

不管是多次查找,还是单次查找,个人感觉,累计起码10K吧查找十次不同的1K
或者,查找一次10K...

只是个人感觉.没有测试

shuimiao

我也有类似算法，不过没有名字，自己想的算法。也是先初始化要查找的目标文本，建一个表，后面大量查找子文本的操作就能提速百倍千倍。而对于每次查找换一个目标文本的场景，这种算法反而更慢。所以是特定用途

小蜗牛

shuimiao 发表于 2024-3-14 09:40
我也有类似算法，不过没有名字，自己想的算法。也是先初始化要查找的目标文本，建一个表，后面大量查找子文 ...

嗯,你这个百倍有点猛啊