c++ - 使用Levenshtein距离算法建议匹配的字符串太慢

Question

我有一个那个函数根据用户提供的字符串返回一个sf::EventType。如果不匹配，则函数返回sf::nullopt。但是我想打印一个建议的，有效的sf::EventType，它与用户提供的内容最接近，以帮助解决拼写错误等问题。

只有“13”个有效的sf::EventType才需要检查是否最接近，并且我假设用户不会输入一些可笑的长字符串。

在我的笔记本电脑m3-7Y30英特尔处理器上，我已经测试了调试和 Release模式下的功能速度:

调试约45秒
释放约3秒

差异很大，但考虑到用户可能提供5到100种事件类型，我仍然觉得3秒有点长。

鉴于这些结果，我怀疑这种建议有效的sf::EventType的方法是否可以进行充分优化以使其可行，但如果可以，我想知道如何。如果没有，我想提出一个建议，无论提供的字符串有多远，它仍然会打印一个建议。

相关代码如下:

convertToSfEvent

std::optional<sf::Event::EventType> EventFileReader::convertToSfEvent(std::string_view event)
    {
        if      (event == "Closed")              return sf::Event::EventType::Closed;
        else if (event == "Resized")             return sf::Event::EventType::Resized;
        else if (event == "LostFocus")           return sf::Event::EventType::LostFocus;
        else if (event == "GainedFocus")         return sf::Event::EventType::GainedFocus;
        else if (event == "TextEntered")         return sf::Event::EventType::TextEntered;
        else if (event == "KeyPressed")          return sf::Event::EventType::KeyPressed;
        else if (event == "KeyReleased")         return sf::Event::EventType::KeyReleased;
        else if (event == "MouseWheelScrolled")  return sf::Event::EventType::MouseWheelScrolled;
        else if (event == "MouseButtonPressed")  return sf::Event::EventType::MouseButtonPressed;
        else if (event == "MouseButtonReleased") return sf::Event::EventType::MouseButtonReleased;
        else if (event == "MouseMoved")          return sf::Event::EventType::MouseMoved;
        else if (event == "MouseEntered")        return sf::Event::EventType::MouseEntered;
        else if (event == "MouseLeft")           return sf::Event::EventType::MouseLeft;
        else
        {
            // Heres is where I search for a match, and the recursion madness starts
            auto smallest_required_change{ INT_MAX };
            auto closest_string{ std::string() };
            for (auto event_type : this->event_types)
            {
                auto result{ levensteinDistance(event, event_type, event.length(), event_type.length()) };

                if (result < smallest_required_change)
                {
                    smallest_required_change = result;
                    closest_string = event_type;
                }
            }

            std::cerr << "Could not recognize event_type token: '" << event << "' did you mean: '" << closest_string << "'?" << "\n";

            return std::nullopt;
        }
    }

距离

std::size_t EventFileReader::levensteinDistance(std::string_view first, std::string_view second, std::size_t first_pos, std::size_t second_pos)
    {
        static auto one{ std::size_t(1) };

        if (!first_pos)
            return first_pos;

        if (!second_pos)
            return second_pos;

        if (first[first_pos - one] == second[second_pos - one])
            return levensteinDistance(first, second, first_pos - one, second_pos - one);

        return 1 + std::min({ levensteinDistance(first, second, first_pos,       second_pos - one),
                              levensteinDistance(first, second, first_pos - one, second_pos),
                              levensteinDistance(first, second, first_pos - one, second_pos - one)
                           });
    }

Answer 1

您的levenshtein实现是递归且缓慢的，例如，您可能需要将其更改为更快的实现(来源:https://rosettacode.org/wiki/Levenshtein_distance):

// Compute Levenshtein Distance
// Martin Ettl, 2012-10-05

size_t uiLevenshteinDistance(const std::string &s1, const std::string &s2)
{
  const size_t m(s1.size());
  const size_t n(s2.size());

  if( m==0 ) return n;
  if( n==0 ) return m;

  size_t *costs = new size_t[n + 1];

  for( size_t k=0; k<=n; k++ ) costs[k] = k;

  size_t i = 0;
  for ( std::string::const_iterator it1 = s1.begin(); it1 != s1.end(); ++it1, ++i )
  {
    costs[0] = i+1;
    size_t corner = i;

    size_t j = 0;
    for ( std::string::const_iterator it2 = s2.begin(); it2 != s2.end(); ++it2, ++j )
    {
      size_t upper = costs[j+1];
      if( *it1 == *it2 )
      {
          costs[j+1] = corner;
      }
      else
      {
        size_t t(upper<corner?upper:corner);
        costs[j+1] = (costs[j]<t?costs[j]:t)+1;
      }

      corner = upper;
    }
  }

  size_t result = costs[n];
  delete [] costs;

  return result;
}

或者，您可以在此页面上寻找灵感:https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#C