DjangoBB LoFi version

Полная версия: Алгоритм расстановки страниц в сканированных книгах

Начало » Центр помощи » Алгоритм расстановки страниц в сканированных книгах

run

Июнь 10, 2014 07:15:33

Здравствуйте !
Есть не то что алгоритмы, но уже и готовые реализации (программа) поэтому не хотелось бы изобретать велосипед.
Но как это сделать на Питоне по правильному ?
исходные данные такие: каждый элемент это порядковый номер файла в книге и номер страницы который получилось считать с этого файла.

parr=[[0,1],[0,2],[0,3],[2,4],[3,5],[4,6],[5,7],[0,8],[0,9],[8,10],[9,11],[11,12],[12,13]]

нужно получить правильную нумерацию страниц в книге (т.е. номер в списке -1 = номеру страницы в книге)

ideal=[[0,3],[2,4],[3,5],[4,6],[5,7],[0,8],[0,9],[8,10],[9,11],[0,0],[11,12],[12,13],[0,1],[0,2]]

т.е. первые два элемента убрать в конец списка и сделать вставку на месте 10 элемента (страница типа пропущена). В конечном итоге получить номер файла в книге = номеру страницы в книге.

Спасибо !

Shaman

Июнь 10, 2014 07:35:07

Напрашивается применение словарей.

doza_and

Июнь 10, 2014 08:07:58

При готовой программе самое правильное пользоваться программой. Но по крайней мере пока не появятся потребности которые она не удовлетворяет.

Так что напишите нам почему надо писать на питоне.

Возможные причины:
1 Требуется массовые перенумерации - представленная программа с gui для этого непригодна.
2 Требуются модификации алгоритма упорядочивания которые проще вставлять в интерпретируемый код
ну и т.п.

По поводу списков.
Мне непонятно почему надо первые 2 элемента переносить в конец. Вот если бы было

parr=[[None,1],[None,2],[0,3],....

тогда понятно, номера страниц не распознаны и переносим их в конец.

Упорядочивание можно сделать функцией sort,sorted

sorted(parr,key=lambda x:x[0])

Необходимость вставок для меня не очевидна. Я бы не стал вставлять пустые листы.
Вставку проще провести если ввести dict который переводит номер страницы в номер файла

dkt = dict(parr)
pages=set(dkt.keys())
maxpage=max(dkt.keys())
allpages=range(1,maxpage)
skippedpages = allpages.difference(pages)
for i in skippedpages:
     dkt[i]=0

run

Июнь 10, 2014 09:57:14

2 doza_and
Почему на питоне ? и первая и вторая причина )
На самом деле реальность сложнее, часто бывает что номер страницы распознается неверно.
В данном алгоритме значения второстепенны, а важно то что элементы следуют в определенном порядке. Поэтому словарь мне кажется не пойдет. Тут скорее надо каким-то образом распределять номера страниц в списке и выбирать тот вариант расстановки в котором максимальное кол-во совпадений номера по списку и номера страницы, который был извлечен из текста. Важное условие - можно перемещать в конец списка страницы которые идут в начале, такое часто бывает когда в книге есть например в начале оглавление пронумерованное римскими цифрами. И можно перемещать в конец когда страницы просто лишние и без нумерации (такое бывает когда в книге есть вставки с рекламой и т.д. т.е. не нумерованнные)
Нет у меня подходящего образования, поэтому какой алгоритм взять за основу не соображу.
Есть еще мысли ? Заранее спасибо.

Shaman

Июнь 10, 2014 10:38:54

Мне кажется, задача нумерации страниц на основании их содержания полной автоматизации не подлежит.

run

Июнь 10, 2014 10:58:11

Подлежит, но с правильностью в некоторое количество процентов, которое хотелось бы иметь как можно выше

Shaman

Июнь 10, 2014 11:07:28

run
но с правильностью в некоторое количество процентов

Это и есть неполная автоматизация.