有效地检查一个字符串是否是另一个字符串的近似子字符串（近似约束在另一个字符串中），直到给定的错误阈值？

Question

取两个 C 或 C++ 字符串，s1并且s2. 检查一个是否完全包含另一个是相当简单的。

true如果s2是 的子字符串，则返回以下内容s1。

在C中：

strstr(s1, s2)

在 C++ 中：

#include <string>
str.find(str2) != string::npos

随着升压：

#include <boost/algorithm/string.hpp>
boost::algorithm::contains(s1, s2)

我正在寻找的是一种类似的方法，可以有效地（在速度方面，而不是内存方面）查找一个字符串是否大约包含在 / 大约是另一个字符串的子串中，直到给定的差异阈值。agrep与 Unix 系统中查找文件的 bash 命令非常相似。

例如，假设该函数被称为approx_contains. 如果包含在编辑距离最多为 4 的范围内，则approx_contains(s1, s2, 4)可以返回 true/false 。s2s1

在网上搜索时，我只发现了大量关于如何计算两个字符串之间的 Levenshtein 距离的参考文献和问题，或者关于近似字符串模式匹配的理论算法，这些算法不仅仅是简单地检查一个字符串是否包含另一个字符串 - 这在这里变得浪费。

非常努力地避免重新发明轮子，怎么可能有人在 C 或 C++ 中进行这样的检查？

Answer 1

我几年前制作了一个测试程序，但它仍然有效。模式的长度受限于 CPU 寄存器中的位数。此处描述：https: //en.wikipedia.org/wiki/Bitap_algorithm。在本网站的“另请参阅”部分中，有一个开源库的链接，https://en.wikipedia.org/wiki/TRE_(computing)

#include <iostream>
#include <string>
#include <vector>
#include <ctype.h>

using namespace std;

typedef unsigned int     UINT;
typedef unsigned __int64 UINT64;

// #define WIDECHAR

#if defined(WIDECHAR)
typedef wstring       String;
typedef wchar_t       Char;
#define CIN           wcin
#define COUT          wcout
#else
typedef string        String;
typedef unsigned char Char;
#define CIN           cin
#define COUT          cout
#endif

template<typename T> T inputValue(const char *prompt) {
  for(;;) {
    COUT << prompt;
    T value;
    CIN >> value;
    if(CIN) return value;
    CIN.clear();
  }
}

// https://en.wikipedia.org/wiki/Bitap_algorithm

class ShiftOr {
private:
#if defined(WIDECHAR)
  static constexpr size_t s_masklength = (0xffff + 1);
#else
  static constexpr size_t s_masklength = (0xff + 1);
#endif // WIDECHAR
  UINT64   m_s;
  UINT     m_patternLen;
  UINT64  *m_mask;

  static constexpr size_t s_maskSizeInBytes = s_masklength * sizeof(m_mask[0]);

  void initMask(const UINT64 *src = nullptr) {
    if(m_mask == nullptr) {
      m_mask = new UINT64[s_masklength];
    }
    if(src) {
      memcpy(m_mask, src, s_maskSizeInBytes); // copy all value from src into m_mask
    } else {
      memset(m_mask, -1, s_maskSizeInBytes); // set all bits in m_mask-array to 1
    }
  }
  void deallocMask() {
    delete[] m_mask;
  }
public:
  ShiftOr()
    : m_s(         0      )
    , m_patternLen(0      )
    , m_mask(      nullptr)
  {
  }
  ShiftOr(const ShiftOr &src)
    : m_s(         src.m_s         )
    , m_patternLen(src.m_patternLen)
    , m_mask(      nullptr         )
  {
    if(src.m_mask) {
      initMask(src.m_mask);
    }
  }
  ShiftOr(const String &pattern, bool ignoreCase=false)
    : m_s(         0      )
    , m_patternLen(0      )
    , m_mask(      nullptr)
  {
    compilePattern(pattern, ignoreCase);
  }
  ShiftOr &operator=(const ShiftOr &src) {
    m_s          = src.m_s;
    m_patternLen = src.m_patternLen;
    if(src.m_mask) {
      initMask(src.m_mask);
    } else {
      deallocMask();
    }
    return *this;
  }
  virtual ~ShiftOr() {
    deallocMask();
  }
  void     compilePattern(const String &pattern, bool ignoreCase=false);
  intptr_t search(        const String &str                           ) const;
  intptr_t searchApprox(  const String &str, UINT maxErrors           ) const;
};

void ShiftOr::compilePattern(const String &pattern, bool ignoreCase) {
  m_patternLen = (UINT)pattern.length();
  if(m_patternLen >= 64) {
    throw string("pattern too long for shiftor-search. max length is 63");
  }
  initMask();
  for(UINT i = 0; i < m_patternLen; i++) {
    const Char ch = pattern[i];
    m_mask[ch] &= ~((UINT64)1 << i);
    if(ignoreCase) {
      if(iswlower(ch)) {
        m_mask[_toupper(ch)] &= ~((UINT64)1 << i);
      } else if(isupper(ch)) {
        m_mask[_tolower(ch)] &= ~((UINT64)1 << i);
      }
    }
  }
  m_s = (UINT64)1 << m_patternLen;
}

intptr_t ShiftOr::search(const String &str) const {
  const UINT64 maskEnd  = m_s;
  UINT64       s        = ~1;
  const Char *start = (Char*)str.c_str(), *end = start + str.length();
  for(const Char *cp = start; cp < end;) {
    s = (s | m_mask[*(cp++)]) << 1;
    if((s & maskEnd) == 0) {
      return cp - start - m_patternLen;
    }
  }
  return -1;
}

intptr_t ShiftOr::searchApprox(const String &str, UINT maxErrors) const {
  if(maxErrors == 0) {
    return search(str);
  }
  const UINT64     maskEnd  = m_s;
  vector<UINT64>   s;
  for(UINT i = 0; i < maxErrors + 1; i++) {
    s.push_back((UINT64)~1);
  }
  UINT64 *sfirst = s.data(), *slast = sfirst + maxErrors;
  const Char *firstChar = (Char*)str.c_str(), *lastChar = firstChar + str.length();
  for(const Char *cp = firstChar; cp < lastChar;) {
    const UINT64 mask = m_mask[*cp++];
    UINT64      *sp   = sfirst, olds = *sfirst;
    *sp = (olds | mask) << 1;

    while(sp++ < slast) {
      const UINT64 tmp = *sp;
      /* Substitution is all we care about */
      *sp = (olds & (tmp | mask)) << 1;
      olds = tmp;
    }
    if((*slast & maskEnd) == 0) {
      return cp - firstChar - m_patternLen;
    }
  }
  return -1;
}

int main(int argc, char **argv) {
  for(;;) {
    const String   pattern    = inputValue<String>("Enter pattern:");
    const bool     ignoreCase = inputValue<Char>("Ignore case[yn]:") == 'y';
    const ShiftOr  A(pattern, ignoreCase);
    const UINT     maxErrors  = inputValue<UINT>("Enter maxErrors:");
    for(;;) {
      const String text = inputValue<String>("Enter text:");
      if((text.length() > 0) && text[0] == '!') {
        break;
      }
      const intptr_t i = A.searchApprox(text,maxErrors);
      cout << "result:" << i << endl;
    }
  }
  return 0;
}