Есть ли альтернатива `difflib.get_close_matches()`, которая возвращает индексы (позиции в списке) вместо списка строк?

Я хочу использовать что-то вроде difflib.get_close_matches, но вместо наиболее похожие строки, я хотел бы получить индексы (т.е. позицию в списке).

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

Например, вместо:

>>> words = ['hello', 'Hallo', 'hi', 'house', 'key', 'screen', 'hallo', 'question', 'format']
>>> difflib.get_close_matches('Hello', words)
['hello', 'hallo', 'Hallo']

Мне бы хотелось:

>>> difflib.get_close_matches('Hello', words)
[0, 1, 6]

Кажется, не существует параметра для получения этого результата, есть ли альтернатива difflib.get_close_matches(), которая возвращает индексы?

Мое исследование альтернативы

Я знаю, что могу использовать difflib.SequenceMatcher, а затем сравнивать строки один к одному с ratio (или quick_ratio). Однако я боюсь, что это будет очень неэффективно, потому что:

  1. Мне пришлось бы создать тысячи объектов SequenceMatcher и сравнить их (я ожидаю, что get_close_matches избегает использования класса):

    EDIT: неверно. Я проверил исходный код get_close_matches, он действительно использует SequenceMatcher.

  2. нет отсечки (я предполагаю, что есть оптимизация, которая позволяет избежать расчета коэффициента для всей строки)

    EDIT: частично неверно. Код get_close_matches не содержит серьезных оптимизаций, за исключением использования real_quick_ratio, quick_ratio и ratio вместе. В любом случае я могу легко скопировать оптимизацию в свою функцию. Также я не учел, что у SequenceMatcher есть методы для установки последовательностей: set_seq1, set_seq2, так что по крайней мере мне не придется каждый раз создавать объект.

  3. насколько я понимаю, все библиотеки Python скомпилированы на C, и это повысит производительность.

    EDIT: я совершенно уверен, что это так. Функция находится в папке cpython.

    EDIT: существует небольшая разница (значение p равно 0,030198) между выполнением непосредственно из difflib и копированием функция в файле mydifflib.py.

    ipdb> timeit.repeat("gcm('hello', _vals)", setup="from difflib import get_close_matches as gcm; _vals=['hello', 'Hallo', 'hi', 'house', 'key', 'screen', 'hallo', 'question', 'format']", number=100000, repeat=10)
[13.230449825001415, 13.126462900007027, 12.965455356999882, 12.955717618009658, 13.066136312991148, 12.935014379996574, 13.082025538009475, 12.943519036009093, 13.149949093989562, 12.970130036002956]

ipdb> timeit.repeat("gcm('hello', _vals)", setup="from mydifflib import get_close_matches as gcm; _vals=['hello', 'Hallo', 'hi', 'house', 'key', 'screen', 'hallo', 'question', 'format']", number=100000, repeat=10)
[13.363269686000422, 13.087718107010005, 13.112324478992377, 13.358293497993145, 13.283965317998081, 13.056695280989516, 13.021098569995956, 13.04310674899898, 13.024205000008806, 13.152750282009947]

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


python-3.x python string similarity difflib
person toto_tico    schedule 14.06.2018    source источник

Ответы (2)


arrow_upward
12
arrow_downward

Я взял исходный код для get_close_matches и изменил его. чтобы вернуть индексы вместо строковых значений.

# mydifflib.py
from difflib import SequenceMatcher
from heapq import nlargest as _nlargest

def get_close_matches_indexes(word, possibilities, n=3, cutoff=0.6):
    """Use SequenceMatcher to return a list of the indexes of the best 
    "good enough" matches. word is a sequence for which close matches 
    are desired (typically a string).
    possibilities is a list of sequences against which to match word
    (typically a list of strings).
    Optional arg n (default 3) is the maximum number of close matches to
    return.  n must be > 0.
    Optional arg cutoff (default 0.6) is a float in [0, 1].  Possibilities
    that don't score at least that similar to word are ignored.
    """

    if not n >  0:
        raise ValueError("n must be > 0: %r" % (n,))
    if not 0.0 <= cutoff <= 1.0:
        raise ValueError("cutoff must be in [0.0, 1.0]: %r" % (cutoff,))
    result = []
    s = SequenceMatcher()
    s.set_seq2(word)
    for idx, x in enumerate(possibilities):
        s.set_seq1(x)
        if s.real_quick_ratio() >= cutoff and \
           s.quick_ratio() >= cutoff and \
           s.ratio() >= cutoff:
            result.append((s.ratio(), idx))

    # Move the best scorers to head of list
    result = _nlargest(n, result)

    # Strip scores for the best n matches
    return [x for score, x in result]

Применение

>>> from mydifflib import get_close_matches_indexes
>>> words = ['hello', 'Hallo', 'hi', 'house', 'key', 'screen', 'hallo', 'question', 'format']
>>> get_close_matches_indexes('hello', words)
[0, 1, 6]

Теперь я могу связать эти индексы со связанными данными строки без необходимости поиска в строках.

person toto_tico    schedule 15.06.2018
comment
Шикарный вопрос, классный ответ. Спасибо. - person G. Fougeron; 08.09.2020

arrow_upward
0
arrow_downward

Не точный ответ на ваш вопрос, но я пытался найти более простой индекс одиночного совпадения, и синтаксис

match_string = difflib.get_close_matches(appx_name_str,names_list,n=1,cutoff=0.1)[0]
match_index = names_list.index[match_string] # index method on list of strings
person user15420598    schedule 14.06.2021