Поиск слов в длинной строке на расстоянии редактирования без учета пробелов - PullRequest
Новая
       65

Поиск слов в длинной строке на расстоянии редактирования без учета пробелов

0 голосов
/ 21 февраля 2019

Я ищу алгоритм для эффективного поиска слов в пределах заданного расстояния редактирования в строке запроса , игнорируя пробел .

Для, например, слов, по которым мне нужно построить индексявляются: 

OHIO, WELL

и строка запроса: 

HELLO HI THERE H E L L O WORLD WE LC OME

Для расстояния редактирования 1 мне нужен вывод: 

HELL, O HI T, H E L L, WE LC

Для игнорирования части пробела, возможно, мы можемудалите все пробелы, но я не могу найти ни одного алгоритма, который нечетко ищет текст в строке без пробелов.

Я провел много исследований без какого-либо успеха.Пожалуйста, дайте мне знать, если вопрос неясен или вам нужна дополнительная информация.

1 Ответ

0 голосов
/ 21 февраля 2019 
public static void main(String[] args) {
    System.out.println(getMatches(List.of("OHIO", "WELL"), "HELLO HI THERE H E L L O WORLD WE LC OME", 1));
}

private static List<String> getMatches(List<String> words, String query, int editDistance) {
    return words.stream()
            .flatMap(w -> getMatches(w, query, editDistance).stream().map(String::trim))
            .distinct()
            .collect(Collectors.toList());
}

private static List<String> getMatches(String word, String query, int editDistance) {
    List<String> matches = new ArrayList<>();
    for (int i = 0; i < query.length(); i++) {
        StringBuilder candidate = new StringBuilder();
        StringBuilder candidateWithoutSpaces = new StringBuilder();
        populateCandidates(word, query, i, candidate, candidateWithoutSpaces);
        if (isMatch(candidateWithoutSpaces, word, editDistance)) matches.add(candidate.toString());
    }
    return matches;
}

private static boolean isMatch(StringBuilder candidateWithoutSpaces, String word, int editDistance) {
    if (candidateWithoutSpaces.length() != word.length()) return false;
    for (int i = 0; i < candidateWithoutSpaces.length(); i++) {
        if (candidateWithoutSpaces.charAt(i) != word.charAt(i) && --editDistance < 0) return false;
    }
    return true;
}

private static void populateCandidates(String word, String query, int i, StringBuilder candidate, StringBuilder candidateWithoutSpaces) {
    int j = 0;
    while (candidateWithoutSpaces.length() < word.length() && i + j < query.length()) {
        char c = query.charAt(i + j);
        candidate.append(c);
        if (c != ' ') candidateWithoutSpaces.append(c);
        j++;
    }
}

Выход 

[O HI T, HELL, H E L L, WE LC]
...