grup string yang hampir duplikat

Question

Saya menggunakan skrip berikut untuk mencari fuzzy nama buku yang hampir mirip untuk duplikat:

import re
from nltk.util import ngrams

OriginalBooksList = list()
booksAfterRemovingStopWords = list()
booksWithNGrams = list()
duplicatesSorted = list()

stopWords = ['I', 'a', 'about', 'an', 'are', 'as', 'at', 'be', 'by', 'com', 'for', 'from', 'how', 'in', 'is', 'it', 'of', 'on', 'or', 'that', 'the', 'this', 'to', 'was', 'the',
             'and', 'A', 'About', 'An', 'Are', 'As', 'At', 'Be', 'By', 'Com', 'For', 'From', 'How', 'In', 'Is', 'It', 'Of', 'On', 'Or', 'That', 'The', 'This', 'To', 'Was', 'The', 'And']

with open('UnifiedBookList.txt') as fin:
    for line_no, line in enumerate(fin):
        OriginalBooksList.append(line)
        line = re.sub(r'[^\w\s]', ' ', line)  # replace punctuation with space
        line = re.sub(' +', ' ', line)  # replace multiple space with one
        line = line.lower()  # to lower case
        if line.strip() and len(line.split()) > 2:  # line can not be empty and line must have more than 2 words
            booksAfterRemovingStopWords.append(' '.join([i for i in line.split(
            ) if i not in stopWords]))  # Remove Stop Words And Make Sentence


for line_no, line in enumerate(booksAfterRemovingStopWords):
    tokens = line.split(" ")
    output = list(ngrams(tokens, 3))
    temp = list()

    temp.append(OriginalBooksList[line_no])  # Adding original line
    for x in output:  # Adding n-grams
        temp.append(' '.join(x))
    booksWithNGrams.append(temp)

while booksWithNGrams:
    first_element = booksWithNGrams.pop(0)
    x = 0
    for mylist in booksWithNGrams:
        if set(first_element) & set(mylist):
            if x == 0:
                duplicatesSorted.append(first_element[0])
                x = 1
            duplicatesSorted.append(mylist[0])
            booksWithNGrams.remove(mylist)
    x = 0

with open('DuplicatesSorted.txt', 'w') as f:
    for item in duplicatesSorted:
        f.write("%s\n" % item)

Masukannya adalah:

A Course of Pure Mathematics by G. H. Hardy
Agile Software Development, Principles, Patterns, and Practices by Robert C. Martin
Advanced Programming in the UNIX Environment, 3rd Edition
Advanced Selling Strategies: Brian Tracy
Advanced Programming in the UNIX(R) Environment
Alex's Adventures in Numberland: Dispatches from the Wonderful World of Mathematics by Alex Bellos, Andy Riley
Advertising Secrets of the Written Word: The Ultimate Resource on How to Write Powerful Advertising
Agile Software Development, Principles, Patterns, and Practices
A Course of Pure Mathematics (Cambridge Mathematical Library) 10th Edition by G. H. Hardy 
Alex’s Adventures in Numberland
Advertising Secrets of the Written Word
Alex's Adventures in Numberland Paperback by Alex Bellos

Outputnya adalah:

A Course of Pure Mathematics by G. H. Hardy

A Course of Pure Mathematics (Cambridge Mathematical Library) 10th Edition by G. H. Hardy 

Agile Software Development, Principles, Patterns, and Practices by Robert C. Martin

Agile Software Development, Principles, Patterns, and Practices

Advanced Programming in the UNIX Environment, 3rd Edition

Advanced Programming in the UNIX(R) Environment

Alex's Adventures in Numberland: Dispatches from the Wonderful World of Mathematics by Alex Bellos, Andy Riley

Alex’s Adventures in Numberland

Alex's Adventures in Numberland Paperback by Alex Bellos

Advertising Secrets of the Written Word: The Ultimate Resource on How to Write Powerful Advertising

Advertising Secrets of the Written Word

Dengan melihat naskahnya, bagi saya sepertinya saya mengalami banyak hal yang rumit. Tolong beri beberapa saran tentang bagaimana saya bisa membuat kode ini lebih baik.

Answer 1

Oke, saya mencoba mengatur ulang sedikit:

1. Kata henti yang diperbaiki (Seharusnya hanya berisi kata-kata kecil)
2. Metode Jaccard digunakan untuk menghitung jarak
3. Struktur kode ulang
4. Tulis ulang dengan Python3 dengan anotasi tipe

Anda sekarang harus menambahkan parser argumen dan pada dasarnya itu.

Sejauh yang saya mengerti tugasnya, tujuan akhirnya adalah menghapus buku yang sama.

Sekarang Anda bisa bermain dengan thresholdargumen untuk mencari tahu string apa yang harus diperlakukan sama.

import re
from typing import List, Callable, Set

from nltk.metrics.distance import jaccard_distance
from nltk.util import ngrams


def canonize(data: str) -> str:
    data = re.sub(r'[^\w\s]', ' ', data)  # replace punctuation with space
    data = re.sub(' +', ' ', data)  # replace multiple space with one
    return data.lower().strip()


def jaccard(book_a: str, book_b: str, n: int = 3) -> float:
    return 1 - jaccard_distance(set(ngrams(book_a, n)), set(ngrams(book_b, n)))


def filter_books(books: List[str],
                 book_filter_fun: Callable,
                 cmp_filter_func: Callable,
                 threshold: float = 0.3) -> Set[int]:
    excluded_indices = set()
    for one_book_offset, one_book in enumerate(books):
        if book_filter_fun(one_book):
            excluded_indices.add(one_book_offset)
        for another_book_offset, another_book in enumerate(books[one_book_offset + 1:], start=one_book_offset + 1):
            if {one_book_offset, another_book_offset} & excluded_indices:
                continue
            if cmp_filter_func(one_book, another_book) > threshold:
                excluded_indices.add(one_book_offset)
    return excluded_indices


if __name__ == '__main__':
    stopWords = {'i', 'a', 'about', 'an', 'are', 'as', 'at', 'be', 'by', 'com', 'for', 'from', 'how', 'in', 'is', 'it',
                 'of', 'on', 'or', 'that', 'the', 'this', 'to', 'was', 'the'}

    with open('UnifiedBookList.txt') as fin:
        original_books = fin.readlines()

    canonized_books = list(map(canonize, original_books))

    excluded_indices = filter_books(
        canonized_books,
        lambda book: len(book.split()) < 2,  # book name should contain not less than 2 words
        jaccard,
    )

    with open('DuplicatesSorted.txt', 'w') as fout:
        for i, book in enumerate(original_books):
            if i in excluded_indices:
                continue
            fout.write(book)

Answer 2

Dari kode tersebut, sepertinya kriteria untuk mengatakan buku-buku tersebut cocok adalah bahwa mereka memiliki setidaknya satu n-gram yang cocok. Karena itu, kodenya bisa sedikit disederhanakan.

Pada dasarnya, bangun struktur data karena data buku dibaca baris demi baris. Setiap entri memiliki nama buku dan himpunan n-gram.

Kemudian cari n-gram berpotongan. Pantau item yang sudah cocok, sehingga tidak akan diproses lagi.

NAME = 0
NGRAM = 1
NGRAMSIZE = 3

book_data = []

with io.StringIO('\n'.join(data)) as fin:
    for line in fin:
        line = line.strip()
        words = re.findall(r'\w+', line.lower())
        good_words = tuple(w for w in words if w not in stopwords)
        n_grams = set(ngrams(good_words, NGRAMSIZE))
     
        book_data.append((line, n_grams))

used_indices = set()
grouped_books = []

for index, (_, book_ngrams) in enumerate(book_data):
    if index in used_indices:
        continue

    grouped_books.append(index)
    used_indices.add(index)
    
    for other_index, (_, other_ngrams) in enumerate(book_data[index + 1:], index + 1):
        if book_ngrams & other_ngrams:
            grouped_books.append(other_index)
            used_indices.add(other_index)
        
for index in grouped_books:
    print(f"{index:2} {book_data[index][NAME]}")

Anda juga dapat mempertimbangkan untuk menggunakan difflibdari pustaka standar. Berikut beberapa kode untuk menunjukkan bagaimana kode itu dapat digunakan.

def isjunk (word): mengembalikan word.lower () bukan dalam stopwords

matcher = dl.SequenceMatcher(isjunk=isjunk)

with open('datafile.txt') as f:
    books = [line.lower()) for line in f]    

titles = [re.findall(r'\w+', book) for book in books]

for i, seq2 in enumerate(titles):
        
    print('\n', i, books[i], '\n')
    
    matcher.set_seq2(seq2)
    
    for j, seq1 in enumerate(titles[i+1:], i+1):
        matcher.set_seq1(seq1)
        
        score = matcher.ratio()
        if score > 0.4:
            print(f"  {j:2} {score:4.2f} {books[j]}")