Самый эффективный алгоритм для поиска первого совпадения префикса из отсортированного массива строк?

Question

Введите:

1) Огромный отсортированный массив строк SA;

2) Строка префикса P;

Выход:

Индекс первой строки, соответствующей входному префиксу, если есть. Если такого совпадения нет, вывод будет -1.

Пример:

SA = {"ab", "abd", "abdf", "abz"}
P = "abd"

Вывод должен быть 1 (индекс начинается с 0).

Какой алгоритм наиболее подходит для выполнения такой работы?

Answer 1

Если вы хотите сделать это только один раз, используйте бинарный поиск , если, с другой стороны, вам нужно сделать это для множества разных префиксов, но для одного и того же массива строк, создавая радикальное дерево может быть хорошей идеей, после того как вы построите дерево, каждый поиск будет очень быстрым.

Answer 2

Это можно сделать за линейное время, используя Дерево суффиксов . Построение дерева суффиксов занимает линейное время.

Answer 3

Это просто модифицированный поиск по разделению пополам:

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

Answer 4

Вот возможное решение (в Python), которое имеет O (k.log (n)) сложность времени и O (1) сложность дополнительного пространства (с учетом n строк) и длина префикса k).

Логическое обоснование для выполнения бинарного поиска, который учитывает только заданный символьный индекс строк. Если они присутствуют, перейдите к следующему символьному указателю. Если какой-либо из префиксных символов не может быть найден ни в одной строке, он немедленно возвращается.

from typing import List

def first(items: List[str], prefix: str, i: int, c: str, left: int, right: int):
    result = -1

    while left <= right:
        mid = left + ((right - left) // 2)
        if ( i >= len(items[mid]) ):
            left = mid + 1
        elif (c < items[mid][i]):
            right = mid - 1
        elif (c > items[mid][i]):
            left = mid + 1
        else:
            result = mid
            right = mid - 1

    return result

def last(items: List[str], prefix: str, i: int, c: str, left: int, right: int):
    result = -1

    while left <= right:
        mid = left + ((right - left) // 2)
        if ( i >= len(items[mid]) ):
            left = mid + 1
        elif (c < items[mid][i]):
            right = mid - 1
        elif (c > items[mid][i]):
            left = mid + 1
        else:
            result = mid
            left = mid + 1

    return result

def is_prefix(items: List[str], prefix: str):
    left = 0
    right = len(items) - 1
    for i in range(len(prefix)):
        c = prefix[i]
        left = first(items, prefix, i, c, left, right)
        right = last(items, prefix, i, c, left, right)

        if (left == -1 or right == -1):
            return False

    return True

# Test cases
a = ['ab', 'abjsiohjd', 'abikshdiu', 'ashdi','abcde Aasioudhf', 'abcdefgOAJ', 'aa', 'aaap', 'aas', 'asd', 'bbbbb', 'bsadiojh', 'iod', '0asdn', 'asdjd', 'bqw', 'ba']
a.sort()
print(a)
print(is_prefix(a, 'abcdf'))
print(is_prefix(a, 'abcde'))
print(is_prefix(a, 'abcdef'))
print(is_prefix(a, 'abcdefg'))
print(is_prefix(a, 'abcdefgh'))
print(is_prefix(a, 'abcde Aa'))
print(is_prefix(a, 'iod'))
print(is_prefix(a, 'ZZZZZZiod'))

Эта суть доступна на https://gist.github.com/lopespm/9790d60492aff25ea0960fe9ed389c0f

Answer 5

Мое решение: Используется бинарный поиск.

private static int search(String[] words, String searchPrefix) {

        if (words == null || words.length == 0) {
            return -1;
        }
        int low = 0;
        int high = words.length - 1;
        int searchPrefixLength = searchPrefix.length();

        while (low <= high) {
            int mid = low + (high - low) / 2;

            String word = words[mid];
            int compare = -1;

            if (searchPrefixLength <= word.length()) {
                compare = word.substring(0, searchPrefixLength).compareTo(searchPrefix);
            }

            if (compare == 0) {
                return mid;
            } else if (compare > 0) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }

        }
        return -1;
    }

Answer 6

Вы в состоянии предварительно рассчитать все возможные префиксы?

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

Answer 7

Мое текущее решение заключается в том, чтобы вместо «префикса» попытаться найти «виртуальный префикс».

Например, префикс «abd», попробуйте найти виртуальный префикс «abc (255)». (255) просто представляет максимальное число символов. После нахождения «abc (255)». Следующее слово должно быть первым словом, соответствующим «abd», если оно есть.

Answer 8

Ядро FreeBSD использует Radix tree для своей таблицы маршрутизации, вы должны проверить это.