Сходство строк с Python + Sqlite (расстояние Левенштейна/расстояние редактирования) ⇐ Python

[Anonymous]

Существует ли в Python+Sqlite мера сходства строк, например, с помощью модуля sqlite3?

Пример использования:

Код: Выделить всё

import sqlite3
conn = sqlite3.connect(':memory:')
c = conn.cursor()
c.execute('CREATE TABLE mytable (id integer, description text)')
c.execute('INSERT INTO mytable VALUES (1, "hello world, guys")')
c.execute('INSERT INTO mytable VALUES (2, "hello there everybody")')

Этот запрос должен соответствовать строке с идентификатором 1, но не строке с идентификатором 2:

Код: Выделить всё

c.execute('SELECT * FROM mytable WHERE dist(description, "He lo wrold gyus") < 6')

Как это сделать в Sqlite+Python?

Заметки о том, что я на данный момент нашел:

• Расстояние Левенштейна, т.е. минимальное количество односимвольных правок (вставок, удалений или замен) ), необходимый для замены одного слова на другое, может быть полезен, но я не уверен, существует ли официальная реализация в Sqlite (я видел несколько пользовательских реализаций, таких как эта)
• Дамерау-Левенштейна то же самое, за исключением того, что он также позволяет транспонировать между двумя соседними символами; его также называют расстоянием редактирования
• Я знаю, что можно определить функцию самостоятельно, но реализация такого расстояния будет нетривиальной (выполнение обработки естественного языка сверхэффективное сравнение баз данных на самом деле нетривиально), поэтому я хотел посмотреть, есть ли уже в Python/Sqlite такой инструмент
• Sqlite имеет FTS (Полная версия) Текстовый поиск) функции: FTS3, FTS4, FTS5
  

  Код: Выделить всё

  CREATE VIRTUAL TABLE enrondata1 USING fts3(content TEXT);     /* FTS3 table */
  CREATE TABLE enrondata2(content TEXT);                        /* Ordinary table */
  SELECT count(*) FROM enrondata1 WHERE content MATCH 'linux';  /* 0.03 seconds */
  SELECT count(*) FROM enrondata2 WHERE content LIKE '%linux%'; /* 22.5 seconds */
  

  но я не нашел сравнения строк с таким «расстоянием сходства», функции FTS MATCH или NEAR, похоже, не работают иметь меру сходства с изменением букв и т. д.
• Более того, этот ответ показывает, что:
  
  
  Механизм SQLite FTS основан на токенах — ключевых словах, которым пытается сопоставить поисковая система.
  
  Доступны различные токенизаторы, но они относительно просты. «Простой» токенизатор просто разделяет каждое слово и записывает его в нижний регистр: например, в строке «Быстрая коричневая лиса прыгает через ленивую собаку» будет соответствовать слово «прыгает», но не «прыгать». Токенизатор "porter" немного более продвинут: он удаляет спряжения слов, так что слова "jumps" и "jumping" будут совпадать, но опечатка типа "jmups" не будет совпадать.
  
  
  Последнее (тот факт, что "jmups" нельзя найти похожим на "прыжки"), к сожалению, делает его непрактичным для моего варианта использования.

Подробнее здесь: https://stackoverflow.com/questions/497 ... t-distance