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

  • bunyk
  • Replace Team
  • Поза форумом
  • Звідки: Франик
  • Дата реєстрації: 24.07.2012
  • Повідомлень: 959
    • Репутація: 751

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

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

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

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

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

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

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

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

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

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

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

{приспів}

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

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

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

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

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

bunyk вебсайт

2 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 616
    • Репутація: 13326

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

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

koala вебсайт

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

  • bunyk
  • Replace Team
  • Поза форумом
  • Звідки: Франик
  • Дата реєстрації: 24.07.2012
  • Повідомлень: 959
    • Репутація: 751

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^>'

bunyk вебсайт

4 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 616
    • Репутація: 13326

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

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

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

koala вебсайт

5 Відповідь від bunyk

  • bunyk
  • Replace Team
  • Поза форумом
  • Звідки: Франик
  • Дата реєстрації: 24.07.2012
  • Повідомлень: 959
    • Репутація: 751

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

koala написав:

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

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

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

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

bunyk вебсайт

6 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 616
    • Репутація: 13326

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

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

koala вебсайт

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

  • bunyk
  • Replace Team
  • Поза форумом
  • Звідки: Франик
  • Дата реєстрації: 24.07.2012
  • Повідомлень: 959
    • Репутація: 751

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])

bunyk вебсайт