Allow re-running feed_entry_dedupe

[lemon24]

https://www.cockroachlabs.com/blog/index.xml in my database had a lot of duplicates from about a year ago. I'm not sure if this is because they predate feed_entry_dedupe, or because it didn't detect duplicates (it is pretty strict).

Regardless, after I find out (and fix it), I need a way to rerun the plugin.

[lemon24]

Possible implementation:

1. User adds a .reader.entry_dedupe.once tag/metadata (maybe we can shorten that to .reader.entry_dedupe).
2. A hook checks if the feed has the tag; if it does, it re-runs the plugin, and maybe removes the tag. Two ways to do this:
   • a hook that runs every time a feed gets updated (either before, or after); results in one extra get_feed_tags/_metadata() calls per feed
   • a hook that runs every time update_feeds() gets called; the plugin can get all the feeds by tag, and do stuff on them; probably worse, since it may update other feeds than the ones selected by update_feeds() (and also, it doesn't work with update_feed())

Getting all the entries and simulating them being added (as we do now) is not ideal, since for N entries, it results in N+1 get_entries() calls. A first solution is to use full-text search to get the entries with the same title (results in N search_entries() calls). A better solution is to do only one search_entries() call per entry group (where the entries have the same title).

To do the search_entries() optimization, we need a standard way turning an arbitrary string into a search query that matches it (a sort of query escape). From #122 (comment):

Then, the user can retry with a cleaned up / escaped version of the query string as a last resort (e.g. replace all non-token characters with spaces). This is storage-/search-engine-dependent, though; it would be useful for the search component itself to provide this in some way.

The FTS5 docs say we can use SQL-style double-quotes:

>>> query = 'HI #75: "World’s Most Interesting Podcast"'
>>> [reader.get_entry(e).title for e in reader.search_entries(query)]
Traceback (most recent call last):
  ...
reader.exceptions.InvalidSearchQueryError: fts5: syntax error near "#"
>>> import re
>>> def fts5_escape(string):
...     return '"' + re.sub('"', '""', string) + '"'
... 
>>> fts5_escape(query)
'"HI #75: ""World’s Most Interesting Podcast"""'
>>> [reader.get_entry(e).title for e in reader.search_entries(fts5_escape(query))]
['HI #75: "World’s Most Interesting Podcast"']

To get only the title, we can prefix the thing with title: (outside the quotes; inside doesn't work); note that this syntax is search-dependent as well:

>>> [reader.get_entry(e).title for e in reader.search_entries(f'title:{fts5_escape(query)}')]
['HI #75: "World’s Most Interesting Podcast"']
>>> [reader.get_entry(e).title for e in reader.search_entries(fts5_escape('title:' + query))]
[]

Update: Quoting, already done by sqlite-utils: https://sqlite-utils.datasette.io/en/stable/python-api.html#quoting-characters-for-use-in-search

[lemon24]

Here's a mock-up of what the plugin logic would look like (also with support for #140):

def init_reader(reader):
    reader.after_entry_update_hooks.append(after_entry_update)
    reader.after_feed_update_hooks.append(after_entry_update)

def after_entry_update(reader, entry, status):
    if status != 'added':
        return

    others = list(get_same_group_entries(reader, entry))
    if not others:
        return

    dedupe_entries(reader, entry, others)

def after_feed_update(reader, feed):
    tag = reader.make_reader_reserved_name('entry_dedupe.once')
    tags = set(reader.get_feed_tags(feed))

    if tag not in tags:
        continue

    for entry, others in get_entry_groups(reader, feed)
        if not others:
            continue

        dedupe_entries(reader, entry, others)
        
    reader.remove_feed_tag(tag)
    
COPY_ACTIONS = [copy_read, copy_important, clear_read, clear_important]
DELETE_ACTIONS = [copy_read, copy_important, delete_duplicates]

def dedupe_entries(reader, entry, others):
    duplicates = [e for e in others if is_duplicate(entry, e)]
    if not duplicates:
        return
    
    # here we could DELETE_ACTIONS instead based on config.
    # for dry run, we can make action yield partials instead
    for action in COPY_ACTIONS:
        action(reader, entry, duplicates)

def get_same_group_entries(reader, entry):
    # here we can use the search_entries() optimization instead
    for e in reader.get_entries(feed=entry.feed):
        if e.object_id == entry.object_id:
            continue
        if e.title != entry.title:
            continue
        yield e

def get_entry_groups(reader, feed):
    # get_entries(sort='title') doesn't exist, but can be emulated
    groups = groupby(
        reader.get_entries(feed=feed, sort='title'), 
        key=lambda e: e.title
    )
    # FIXME: this is not entirely correct, we need to group by is_duplicate too
    for _, entries in groups:
        entry, *others = sorted(
            entries, 
            key=lambda e: e.last_updated, 
            reverse=True,
        )
        yield entry, others

def is_duplicate(one, two):
    # we could use a different implementation based on config
    ...

[lemon24]

For my live database, there were 785 entries that maybe had duplicates (based on title only). Without the content similarity check added in 8138931, there were 378 entries that didn't have duplicates; with it, only 92 entries didn't; the word count / similarity scores in the code are based on the tables below.

The tables below show the similarity distribution for Jaccard similarity for 4-grams, after applying successively stricter filters to exclude "unsafe duplicates" (false positives, pathological false negatives, too-short content); the tables were generated with logs from the commented bits here and this script.

This table shows pair distribution per [0.0, 0.1) etc. intervals; the columns mean:

• clean removed known false positives and pathological false negatives
• trim made pairs of content trimmed to the shorter word length
• minX only kept pairs with the word length >= X

	init	clean	trim	min12	min48	min64	min80	min96
0.0	302	14	7	6	5	5	4	2
0.1	14	2	2	2	2	2	2	1
0.2	15	11	10	10	10	10	9	7
0.3	96	95	7	7	7	7	7	6
0.4	136	133	7	7	7	7	7	7
0.5	11	8	6	6	6	6	4	3
0.6	9	8	7	7	6	6	6	6
0.7	12	12	14	14	14	14	11	9
0.8	11	11	35	35	35	35	19	8
0.9	49	48	39	39	39	39	36	34
1.0	nan	nan	208	207	197	188	131	32
entries	382	333	333	332	321	313	230	109
pairs	655	342	342	340	328	319	236	115

This is the same table, but shows how many pairs have a score higher than 0.0 etc. (cumulative difference):

	init	clean	trim	min12	min48	min64	min80	min96
0.0	655	342	342	340	328	319	236	115
0.1	353	328	335	334	323	314	232	113
0.2	339	326	333	332	321	312	230	112
0.3	324	315	323	322	311	302	221	105
0.4	228	220	316	315	304	295	214	99
0.5	92	87	309	308	297	288	207	92
0.6	81	79	303	302	291	282	203	89
0.7	72	71	296	295	285	276	197	83
0.8	60	59	282	281	271	262	186	74
0.9	49	48	247	246	236	227	167	66
1.0	nan	nan	208	207	197	188	131	32
entries	382	333	333	332	321	313	230	109
pairs	655	342	342	340	328	319	236	115

The remaining pairs after clean-up and trimming with sim < 0.8 were all true duplicates (I checked them by hand).

Some interesting cases I found:

• feeds with recurrent entries with the same title (e.g. weekly recurrent post); false positive
  • get skipped because of the threshold
• feeds with 2 entries with same title, one of which has little static content (e.g. due to blog platform change); false negative
  • get skipped because of the threshold and content length check
  • fix needed: mechanism for saying "dedupe only by title, not content"
• feeds with 2 entries with same title, the content of one is exact prefix of the other
  • fix needed: check similarity for common length at the beginning
• feeds where content moved from summary to content
  • handling by checking all summary / content combos and using the best score (new)
• feeds with multiple entries with the same title, and roughly the same content (more stuff appended each time, but different ids on purpose)
  • currently treated as duplicates based on similarity (they are pretty much the same)
• feeds with multiple entries with same title and link
  • link not reliable (e.g. someone puts link to site instead of post)
• entries with HTML escaped twice
  • about half are still similar enough
  • fix needed: mechanism for saying "dedupe only by title, not content"

[lemon24]

To do for this issue:

• after_feed_update_hooks
• entry_dedupe once and once_title_only hooks (tag names TBD)
• entry_dedupe tests
• docs, changelog, comments about possible optimizations