Вернуть все слова, которые можно сгенерировать из заданной строки, добавив диакритические знаки

Question

Предположим, что существует неясный алфавит, основанный на латинице, но с большим количеством диакритических знаков (на самом деле, алфавит, с которым я работаю, основан на кириллице, которая сама по себе достаточно запутана, поэтому я решил пойти с вымышленным латинским примером).

Даже когда устройства поддерживают этот язык, ввод неудобен (вам нужно часто переключать раскладки, использовать комбинации клавиш и т. Д.), Поэтому я хочу дать пользователям возможность использовать для ввода только "обычные" символы. о письмо будет означать о себе, затем -, и т. д.

Например, есть слово "fóobař". Пользователь может ввести только "foobar", и программа должна вернуть некоторые данные для ввода "fóobař".

Я делаю это так:

public static void main(String[] args) {
    HashSet<String> guesses = new HashSet();
    String initial = "foobar";
    generate(initial, 0, guesses);
    System.out.println(guesses);
}

private static void generate(String s, int startFrom, HashSet<String> guesses) {        
    if (startFrom == s.length() - 1) {
        return;
    }
    guesses.add(s);
    for (int i = startFrom; i < s.length(); i++) {
        char[] substitutes = getSubstitutes(s.charAt(i));
        for (char ch : substitutes) {
            String newGuess = replaceCharAt(s, i, ch);
            generate(newGuess, i + 1, guesses);
        }           
    }       
}

private static char[] getSubstitutes(char ch) {
    char[] substitutes;
    switch (ch) {
    case 'o':
        substitutes = new char[] {'ó', 'ö'};
        return substitutes;
    case 'r':
        substitutes = new char[] {'ř'};
        return substitutes;
        default:
            return new char[] {};
    }
}

private static String replaceCharAt(String s, int position, char ch) {      
    return s.substring(0, position) + ch + s.substring(position + 1);
}

То есть я рекурсивно генерирую все возможные замены:

[foóbar, foobař, fóóbar, foobar, foóbař, fööbař, föóbar,
 föobař, fööbar, föóbař, fóóbař, fóöbař, föobar, fóobar,
 foöbař, foöbar, fóobař, fóöbar]

а затем выполнить запрос к базе данных с несколькими условиями WHERE

Есть ли лучший способ сделать это, чем пробовать все возможные значения? Будет ли написание SQLite-функции для REGEXP лучше по производительности?

Answer 1

На стороне базы данных создайте дополнительный столбец с копией вашего слова, но каждый символ преобразуется в его "обычную" версию, например, конвертировать ó, öи т. д. для o,

На самом деле, вероятно, он был бы лучше в качестве вычисляемого столбца, но, похоже, SQLite не поддерживает это.

Затем вы можете просто выполнить то же преобразование для введенного текста и запросить добавленный столбец для преобразованного текста.

Пример:

Word     NormalizedWord
foobar   foobar
foöbar   foobar
fóóbar   foobar

Запрос: fóöbar,

Нормализованный запрос: foobar,

Тогда просто ищите строки, где NormalizedWord является foobar (что будет все вышеперечисленное в этом случае).

---

Вышеуказанный подход заключается в оптимизации времени выполнения - он позволит вам добавить индекс к NormalizedWord с учетом быстрого поиска.

Чтобы оптимизировать использование пространства, вы можете просто сохранить слово и конвертировать на лету в поиске, но для этого потребуется, чтобы вы просматривали все строки независимо, так как это не позволяет выполнять индексацию.

Под "преобразованием на лету" я имею в виду что-то вроде:

SELECT *
FROM Table
WHERE Normalize(Word) = NormalizedInputString