поиск текста с использованием бинарного поиска в Python - PullRequest
Новая
       13

поиск текста с использованием бинарного поиска в Python

1 голос
/ 26 июня 2019

У меня есть несколько имен файлов в списке под названием data.Я хочу прочитать содержимое файла и проверить, появляется ли данный файл (пример - оранжевый) в файле.Мои имена файлов добавляются в список в последовательном порядке, т. Е. Если данный текст «оранжевый» появляется в файле pi.txt (индекс 2), он будет присутствовать во всех файлах и после индекса 2, и конечно же, я хочу получитьиндекс или имя файла, где текст «оранжевый» появился первым.

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

data = ['ae.txt', 'ac.txt', 'pi.txt', 'ad.txt', 'mm.txt', 'ab.txt']
target = "orange"

def binary_search(a, x):
    lo = 0
    hi = len(a)

    while lo < hi:
        mid = (lo + hi) // 2

        if not x in open(a[mid]).read():
            lo = mid + 1
        elif x in open(a[mid]).read():
            hi = mid
        elif mid > 0 and x in open(a[mid-1]).read():
            hi = mid
        else:
            return mid

    return -1

print(binary_search(data, target))



$ cat ae.txt
papaya
guava

$ cat ac.txt 
mango
durian
papaya
guava

$ cat pi.txt 
orange
papaya
guava

$ cat ad.txt 
orange
papaya
guava

$ cat mm.txt 
orange
papaya
guava

$ cat ab.txt 
orange
papaya
guava

Ответы [ 3 ]

1 голос
/ 26 июня 2019

Я думаю, что если условий слишком много, вам удастся получить ожидаемый результат, например: 

data = ['ae.txt', 'ac.txt', 'pi.txt', 'ad.txt', 'mm.txt', 'ab.txt']
target = "orange"

def binary_search(a, x):
    lo = 0
    hi = len(a)

    while lo < hi:
        mid = (lo + hi) // 2
        print(mid)
        if not x in open(a[mid]).read():
            lo = mid + 1

        elif x in open(a[mid]).read():
            hi = mid
        if lo == hi:
            return lo

        print("low : {}; high : {}".format(lo,hi))

    return -1
index = binary_search(data, target)
print("The index where we first found the word orange is {}, the file name is {}".format(index,data[index]))

The index where we first found the word orange is 2, the file name is pi.txt
1 голос
/ 26 июня 2019

Ваш бинарный поиск на самом деле не ищет равенства, поэтому его можно немного упростить: 

def binary_search(files, string):
    lo,hi  = 0,len(files)-1
    while hi>=lo:
        mid     = (hi+lo)//2
        if string in open(files[mid]).read(): 
            hi = mid-1
        else: 
            lo = mid+1
    return lo

Поскольку проверка на равенство отсутствует, hi и lo выполнят условие остановки (hi>=lo), в котором точка lo будет указана в индексе первого матча или на len(files), если есть нет совпадений.

0 голосов
/ 26 июня 2019

Бинарный поиск по файлам работает только в том случае, если ваши файлы уже отсортированы по ключу поиска, который вы используете, а это означает, что файл X [n + 1] не должен иметь данных, лексикографически меньших, чем файл X [n]. В этом случае вам придется просматривать каждый файл вручную, пока вы не пройдете тщательный анализ всех файлов ... или не создадите файл словаря, например, такой: 

'ae.txt', 'ac.txt', 'pi.txt', 'ad.txt', 'mm.txt', 'ab.txt'
durian 1
guava 0-5
mango 1
orange 2-5
papaya 0-5

Первая строка обозначает включенные файлы и дает им индексы посредством позиционирования (например, «ae.txt» находится в позиции 0). Другие строки обозначают индексы файлов, которые включают каждое слово.

Отсюда вы можете прочитать первую строку для имен файлов, выполнить двоичный поиск по строкам, чтобы найти слово, которое вы ищете (вам, вероятно, следует найти способ прочитать определенную строку в O (1), хотя - или поместите их в отдельные файлы словаря, например, для отдельных букв, если их слишком много). Затем определите, обозначен ли индекс имени файла (его расположение в первой строке) в строке слова.

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

...