editdistance.h

Go to the documentation of this file.

 
/* Copyright (C) 2003 Richard Boulton
 * Copyright (C) 2007,2008,2017,2019,2024 Olly Betts
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, see
 * <https://www.gnu.org/licenses/>.
 */
 
#ifndef XAPIAN_INCLUDED_EDITDISTANCE_H
#define XAPIAN_INCLUDED_EDITDISTANCE_H
 
#include <cstdlib>
#include <climits>
#include <vector>
 
#include "omassert.h"
#include "xapian/unicode.h"
 
class EditDistanceCalculator {
    EditDistanceCalculator& operator=(const EditDistanceCalculator&) = delete;
 
    EditDistanceCalculator(const EditDistanceCalculator&) = delete;
 
    std::vector<unsigned> target;
 
    size_t target_bytes;
 
    mutable std::vector<unsigned> utf32;
 
    mutable int* array = nullptr;
 
    typedef unsigned long long freqs_bitmap;
 
    freqs_bitmap target_freqs = 0;
 
    freqs_bitmap target_freqs2 = 0;
 
    static constexpr unsigned FREQS_MASK = sizeof(freqs_bitmap) * 8 - 1;
 
    int calc(const unsigned* ptr, int len, int max_distance) const;
 
  public:
    explicit
    EditDistanceCalculator(std::string_view target_)
        : target_bytes(target_.size()) {
        using Xapian::Utf8Iterator;
        for (Utf8Iterator it(target_); it != Utf8Iterator(); ++it) {
            unsigned ch = *it;
            target.push_back(ch);
            auto bit = freqs_bitmap(1) << (ch & FREQS_MASK);
            target_freqs2 |= (target_freqs & bit);
            target_freqs |= bit;
        }
    }
 
    ~EditDistanceCalculator() {
        delete [] array;
    }
 
    int operator()(const std::string& candidate, int max_distance) const {
        // We have the UTF-32 target in target.
        size_t target_utf32_len = target.size();
 
        // We can quickly rule out some candidates just by comparing
        // lengths since each edit can change the number of UTF-32 characters
        // by at most 1.  But first we check the encoded UTF-8 length of the
        // candidate since we can do that without having to convert it to
        // UTF-32.
 
        // Each Unicode codepoint is 1-4 bytes in UTF-8 and one word in UTF-32,
        // so the number of UTF-32 characters in candidate must be <= the number
        // of bytes of UTF-8.
        if (target_utf32_len > candidate.size() + max_distance) {
            // Candidate too short.
            return INT_MAX;
        }
 
        // Each edit can change the number of UTF-8 bytes by up to 4 (addition
        // or deletion of any character which needs 4 bytes in UTF-8), which
        // gives us an alternative lower bound (which is sometimes tighter and
        // sometimes not) and the tightest upper bound.
        if (target_bytes > candidate.size() + 4 * max_distance) {
            // Candidate too short.
            return INT_MAX;
        }
        if (target_bytes + 4 * max_distance < candidate.size()) {
            // Candidate too long.
            return INT_MAX;
        }
 
        // Now convert to UTF-32.
        utf32.assign(Xapian::Utf8Iterator(candidate), Xapian::Utf8Iterator());
 
        // Check a cheap length-based lower bound based on UTF-32 lengths.
        int lb = std::abs(int(utf32.size()) - int(target_utf32_len));
        if (lb > max_distance) {
            return lb;
        }
 
        // Actually calculate the edit distance.
        return calc(&utf32[0], utf32.size(), max_distance);
    }
};
 
#endif // XAPIAN_INCLUDED_EDITDISTANCE_H