1 Востаннє редагувалося bunyk (06.12.2018 16:54:29)

Тема: Пошук максимального дублювання в тексті

Якось знову помітив статтю вікіпедії яку можна скоротити на пару десятків кілобайт правильним оформленням, замінивши повтори в тексті правильним шаблоном.

І з цього з'явилася задача. Є текст (послідовність символів юнікоду), який може містити повторення. Наприклад:

Ти казала: «В понеділок
Підем разом по барвінок».
Я прийшов, тебе нема,
Підманула-підвела.

Ти ж мене підманула,
Ти ж мене підвела,
Ти ж мене молодого
З ума-розуму звела.

Ти казала у вівторок
Поцілуєш разів сорок,
Я прийшов, тебе нема,
Підманула-підвела.

Ти ж мене підманула,
Ти ж мене підвела,
Ти ж мене молодого
З ума-розуму звела.

Неозброєним оком видно що якщо

# типу python
приспів = """
Ти ж мене підманула,
Ти ж мене підвела,
Ти ж мене молодого
З ума-розуму звела.
"""

то текст можна скоротити до

# все ще python
f"""
Ти казала: «В понеділок
Підем разом по барвінок».
Я прийшов, тебе нема,
Підманула-підвела.

{приспів}

Ти казала у вівторок
Поцілуєш разів сорок,
Я прийшов, тебе нема,
Підманула-підвела.

{приспів}
"""

Як написати функцію, яка для даного тексту, і довжини назви змінної, знаходить якомога довшу порцію тексту що якомога частіше повторюється, так щоб при її заміні змінною цей текст максимально скоротився. Повторююсь, при цьому врахувати те що змінна сама по собі має певну довжину. Я в інтернеті бачив якісь згадки про суфіксні дерева, але поки що не зрозумів як написати такий алгоритм.

Цікаво потім буде його для дампу вікіпедії запустити.

Подякували: Yola1

2

Re: Пошук максимального дублювання в тексті

А чим DEFLATE не вгодив?

3 Востаннє редагувалося bunyk (06.12.2018 16:50:44)

Re: Пошук максимального дублювання в тексті

koala написав:

А чим DEFLATE не вгодив?

b'x\x9c%\x8c\xc1\r\x830\x10\x04[\xb9\x02PZHk`?\x12^Hy\xb8\x0e\x83@\x89\xc0vZ\x98\xed(\x07y\xdc\x9eN7;\n4\x8a\xa2i\xa4\x19\x85\x8d\xaad|i\n\xea\x95\x98\xa9lv\x85\x06\x05>\x1a\xce\xc3\xa7j\xea\x8c\xfc\x87\x9f\
x8a\xec\xc6\xeak\xe6\xf0\xdeNvCb\xb9\x19/2\xe5\xe2X\\\xd1\xd4\xbb\xc6U\xc6\xdb?\xab\x93\x0f\xc5\xfb\x0f\xf6r^>'

4

Re: Пошук максимального дублювання в тексті

Ну так а проблема в чому? Ви хочете зменшити розмір за рахунок читаності. DEFLATE саме це й робить.

Подякували: leofun011

5

Re: Пошук максимального дублювання в тексті

koala написав:

Ну так а проблема в чому? Ви хочете зменшити розмір за рахунок читаності. DEFLATE саме це й робить.

Проблема в тому щоб знайти місця, які написані як для коал, які не вміють читати, тому одне й те саме їм повторюють по 10 разів, і переробити їх для людей, зменшивши розмір і збільшивши зручність читання людьми. (як отут)

+ Просто знайти випадкові копіпасти, плагіат і нагоди створити корисний новий шаблон і взагалі задача цікава.

Думаю треба почати копати десь звідси: https://www.geeksforgeeks.org/suffix-tr … substring/

6

Re: Пошук максимального дублювання в тексті

А, ну то вам не довільні місця в тексті треба шукати, а лише значення ref name. А це значно простіше, звичайного dictionary/map/HashMap вистачить.

7 Востаннє редагувалося bunyk (27.12.2018 18:31:11)

Re: Пошук максимального дублювання в тексті

Ну так, брутфорс підходить:

from collections import Counter
import sys

from pywikibot import Page, Site

SEARCH_WINDOW = 50
def most_common(text):
    counts = Counter(text[i:i + SEARCH_WINDOW] for i in range(len(text) - SEARCH_WINDOW))
    pattern, frequency = counts.most_common(1)[0]

    index = text.find(pattern)

    expand_left = 0
    new_frequency = frequency
    while new_frequency == frequency:
        expand_left += 1
        new_frequency = text.count(text[index - expand_left:index + len(pattern) + expand_left])

    index = index - expand_left + 1

    expand_right = 0
    new_frequency = frequency
    while new_frequency == frequency:
        expand_right += 1
        new_frequency = text.count(text[index:index + len(pattern) + expand_right])

    return text[index:index + len(pattern) + expand_right - 1], frequency

def lint_page(title):
    page = Page(Site(), title)
    pattern, frequency = most_common(page.text)
    print(f'"{pattern}" repeats {frequency} times')

if __name__ == '__main__':
    lint_page(sys.argv[1])