ReSQL.ru
     
powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Четверговый архивариус
15 сообщений из 540, страница 22 из 22
  22  
Четверговый архивариус
    #39996003
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Отсортированный список смежности по 1-2 колонкам. (Текстовый формат я привожу просто в качестве Demo)
На самом деле я буду все текстовые цифры писать в бинарном формате. А бинарь не особо презентабелен
для глаз.

 
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
$ head -n 50 war-and-society-1-2-3-4-adjacency-list.csv 
0;1;2339
1;4;1
1;11;516
1;13;1
1;16;1
1;27;1
1;32;9
1;44;2
1;45;2
1;51;1
1;62;2
1;63;1
1;64;1
1;75;1
1;94;1
1;102;19
1;103;2
1;115;1
1;117;3
1;130;7
1;153;1
1;162;1
1;168;2
1;169;7
1;193;5
1;212;39
1;220;4
1;237;1
1;260;53
1;262;3
1;263;1
1;266;1
1;290;6
1;307;6
1;309;1



Еще фрагмент с хвоста

 

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
$ tail -n 50 war-and-society-1-2-3-4-adjacency-list.csv 
48931;20482;1
48931;22039;1
48931;23920;1
48932;6833;1
48932;13011;1
48932;18334;1
48932;22882;1
48933;9;1
48933;37;1
48933;10262;1
48933;18759;1
48933;25864;1
48933;40546;2
48934;13011;1
48934;21165;1
48935;7127;2
48936;39417;1
48937;9;1
48938;6833;1
48939;18825;1
48940;9;1

...
Рейтинг: 0 / 0
06.09.2020, 16:21
| Ответить | Цитировать | Написать  
Четверговый архивариус
    #39996004
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
В текстовом виде в архиве почти 1 мегабайт. Это тоже проигрыш. Не выходим на оценочные объемы.

Код: sql
1.
2.
3.
-rw-rw-r--  1 mayton mayton    3434824 Sep  6 16:24 war-and-society-1-2-3-4-adjacency-list.csv
-rw-rw-r--  1 mayton mayton     975509 Sep  6 16:24 war-and-society-1-2-3-4-adjacency-list.csv.bz2
-rw-rw-r--  1 mayton mayton     957681 Sep  6 16:24 war-and-society-1-2-3-4-adjacency-list.csv.gz



Будем нормализовывать дальше.
...
Рейтинг: 0 / 0
06.09.2020, 16:30
| Ответить | Цитировать | Написать  
Четверговый архивариус
    #39996007
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Убрал повторы вершины V1. Предположительно есть баги с лишним разделилелем (точка с запятой) но в целом статистика
будет достоверной.

Все еще текстовый режим.

Код: sql
1.
2.
3.
-rw-rw-r--  1 mayton mayton    2345580 Sep  6 16:57 war-and-society-1-2-3-4-adjacency-list.csv
-rw-rw-r--  1 mayton mayton     652938 Sep  6 16:57 war-and-society-1-2-3-4-adjacency-list.csv.bz2
-rw-rw-r--  1 mayton mayton     807305 Sep  6 16:57 war-and-society-1-2-3-4-adjacency-list.csv.gz



 
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
public class GraphAdjacencyListTrieSerializer extends BinaryGraphSerializer {

    static Comparator<Triple<Integer, Integer, Integer>> compareByLeft = Comparator.comparing(Triple::getLeft);

    static Comparator<Triple<Integer, Integer, Integer>> compareByLeftAndMiddle = compareByLeft.thenComparing(Triple::getMiddle);

    static final String OPEN_CONTEXT = "(";
    static final String CLOSE_CONTEXT = ")";
    static final String SPLITTER = ";";
    static final String EOL = "";

    @Override
    public void serialize(@NotNull Graph graph, @NotNull OutputStream outputStream, @NotNull Properties properties) throws IOException {
        OutputStreamWriter osv = new OutputStreamWriter(outputStream, StandardCharsets.UTF_8);
        PrintWriter pw = new PrintWriter(osv);
        Map<String, Integer> map = createVertexIdToNumber(graph);
        Triple<Integer,Integer,Integer> triplePrev = null;
        for(Triple<Integer,Integer,Integer> triple : graph.getEdgeWeigthMap()
                .values()
                .stream().map(
                        edge -> Triple.of(
                            map.get(edge.getV1().getId()),
                            map.get(edge.getV2().getId()),
                            edge.getWeight())
                ).sorted(compareByLeftAndMiddle)
                .collect(Collectors.toList())
        ) {
            if (triplePrev != null) {
                if (triplePrev.getLeft().equals(triple.getLeft())) {
                    pw.printf("%d" + SPLITTER + "%d" + SPLITTER + EOL,
                            triple.getMiddle(),
                            triple.getRight());
                } else {
                    pw.printf(CLOSE_CONTEXT + EOL);
                    pw.printf("%d" + SPLITTER + OPEN_CONTEXT + "%d" + SPLITTER +"%d" + SPLITTER + EOL,
                            triple.getLeft(),
                            triple.getMiddle(),
                            triple.getRight());
                }
            } else {
                pw.printf("%d" + SPLITTER + OPEN_CONTEXT + "%d" + SPLITTER + "%d" + SPLITTER + EOL,
                        triple.getLeft(),
                        triple.getMiddle(),
                        triple.getRight());
            }
            triplePrev = triple;
        }
        pw.printf(CLOSE_CONTEXT);

        osv.close();
    }
}





650 килобайт уже лучше но все еще хреново. Буду пробовать бинарник.
...
Рейтинг: 0 / 0
06.09.2020, 17:06
| Ответить | Цитировать | Написать  
Четверговый архивариус
    #39997930
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Приподниму темку. Я о своём, вряд ли это интересно для сжатия. О нек-рых недостатках псевдо3-граммного кодирования. Т.е. как у меня. Потому что я никогда не преследовал сжатия как цели. Выше я дал пример "дайджеста" 1-го тома. Но это было при фильтрации на (не помню) 8-10 уровне. Итог же 1-го уровня таков.
 
На выходе пограммы получаем словарь+"текст". (В кавычках, поскольку "текст" состоит из ссылок на словарь. Для 1-го уровня это текст в натуре, а для вышестоящих уровней - сами понимаете что, ссылка на ссылку...)

Так вот, кол-во узлов в словаре 1-го уровня 7388 байт. При условии, что к тексту был присоеденён словарь 1-2-3хграмм, полученный из реального словаря русского языка. Только все эти псевдотройки в нижнем регистре, а в исходнике они как есть, включая иностранные слова, пробелы и 13/10. Собственно присоеденённый предопределённый словарь < 30K.

Сложив длину узлов в словаре, получим = 21716 байт. Для сжатия плохо, а "текст" 2-го уровня, полученный из ссылок на словарь, ~535K. Т.о. всё текстовое разнообразие 1-го тома (800K) использует вот эти 7388 единиц.

В результате сегментации узлами оказалось достаточно много одиночных символов. Для примера список топов одиночек по убыванию:
"с '\10' и о л . т е р н я в м л - у п а ь к [ ] й ю н Н д х ( ) ч з ! ш ж"....
В этом списке 1-я половина >100 ссылок, 2-я половина <100.

В аутсайдерах 40 узлов по 1-2 вхождений. Там всякие кавычки, инобуквы и т.п., появившиеся после ухода от UTF-8. Это очень плохо даже для дайджеста. Надо сказать, что всё было конвертировано в win-1251.

Следует понимать, что эти же символы входят и в составные узлы в этом же словаре. А значит их частота как узлов не равна частотному использованию символа в исходнике. Каждый узел 1-го уровня может входить в несколько узлов высоких уровней.

На 8-10 уровне ситуация иная. Как цельные узлы 1 и 2 пробела оказались абсолютными лидерами по частоте использования. Пара 13/10 - в перфой пятёрке лидеров.
Вообще, распределение частотности узлов словарей меняется от уровня к уровню. В целом оно (если можно выразиться) "сходится" сперва к квазиравномерному, а потом и к вырожденному, но не сразу и не плавно, а скачками. Во всяк D-->0, а М и медиана -->1. Для дайджеста нужно учитывать этот неравномерный вклад каждого узла, если фильтровать в разных уровнях. Конечно если мы говорим о естественном языке.
...
Рейтинг: 0 / 0
12.09.2020, 15:42
| Ответить | Цитировать | Написать  
Четверговый архивариус
    #39997961
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Что теперь делать? см. рис.
...
Рейтинг: 0 / 0
12.09.2020, 19:29
| Ответить | Цитировать | Написать  
Четверговый архивариус
    #39997999
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
А я улучшил вывод статистики.

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
graph:
  statistics:
    Vertices: '48955'
    Edges: '258215'
    weightStats: {Max edge weight: 24960.0, AVG edge weight: 1.9452587959647216, Median edge weight: 1.0,
      75-th percentille edge weight: 1.0, 80-th percentille edge weight: 1.0, 85-th percentille edge weight: 2.0,
      90-th percentille edge weight: 2.0, 95-th percentille edge weight: 4.0, 97-th percentille edge weight: 6.0}
    joinsStats: {Max joins: 17607.0, AVG joins: 10.549075681748521, Median joins: 2.0,
      75-th percentille joins: 6.0, 80-th percentille joins: 7.0, 85-th percentille joins: 10.0,
      90-th percentille joins: 14.0, 95-th percentille joins: 26.0, 97-th percentille joins: 41.0}
    nameStats: {Max length: 28.0, AVG length: 8.590460627106562, Median length: 8.0,
      75-th percentille name length: 10.0, 80-th percentille name length: 11.0, 85-th percentille name length: 11.0,
      90-th percentille name length: 12.0, 95-th percentille name length: 13.0, 97-th percentille name length: 14.0}


NameStats - это длина имени узла. Как видим Лев Николаич не использовал слова длиннее 14 символов практически.
...
Рейтинг: 0 / 0
12.09.2020, 23:21
| Ответить | Цитировать | Написать  
Четверговый архивариус
    #40000586
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ценой нечеловеческих усилий я разделил проект поддержки графов и сжатие в разные проекты.
Теперь можно развивать алгоритмы графов полностью отдельно.

Из улучшений. Генерики. Теперь вершина и ребро не имеют хардкодных свойств. Они контейнеры.
...
Рейтинг: 0 / 0
19.09.2020, 22:51
| Ответить | Цитировать | Написать  
Четверговый архивариус
    #40000587
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Выложу. Может кому пригодится.

Проект сжатия текстов на основе марковских цепей после этого пришел в полный развал.
Ничего не собирается. Надо сделать много изменений. Я сейчас пытаюсь выкосить из него хотяб 80%
всех ненужных сорцов чтоб стало меньше кода.
...
Рейтинг: 0 / 0
19.09.2020, 22:59
| Ответить | Цитировать | Написать  
Четверговый архивариус
    #40000588
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Некоторые методы просто выглядят громоздко и их надо уменьшить в размере.
Но в следующей версии я просто подпихну тесты чтоб было покрытие. И после этого можно поиграть в улучшалки.

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
public Edge<V, E> linkEdge(Vertex<V, E> v1, Vertex<V, E> v2) {
        // TODO: Simplify with putIfAbsent
        Vertex<V, E> v1real = v1;
        Vertex<V, E> v2real = v2;
        if (!vertexMap.containsKey(v1.getId())) {
            vertexMap.put(v1.getId(), v1);
        } else {
            v1real = vertexMap.get(v1.getId());
            if (v1.getValue() != null && !v1real.getValue().equals(v1.getValue())) {
                throw new RuntimeException("Unable to link existing vertex id = " + v1.getId() + " with new Value = " + v1.getValue());
            }
        }
        if (!vertexMap.containsKey(v2.getId())) {
            vertexMap.put(v2.getId(), v2);
        } else {
            v2real = vertexMap.get(v2.getId());
            if (v2.getValue() != null && !v2real.getValue().equals(v2.getValue())) {
                throw new RuntimeException("Unable to link existing vertex id = " + v2.getId() + " with new Value = " + v2.getValue());
            }
        }

        // New egdes must be initialized with "neutralElement"
        Edge<V, E>  newEdge = new Edge<>(v1real, v2real, edgeNeutralElement);
        // TODO: Simplify with computeIfPresent()
        if (edgeMap.containsKey(newEdge)) {
            // Existing edges must upgade value according to () -> refreshEdgeFunction
            Edge<V, E> realEdge = edgeMap.get(newEdge);
            realEdge.setValue(refreshEdgeFunction.apply(realEdge.getValue()));
            return realEdge;
        } else {
            // New egdes must be added into vertex lists
            v1real.addOutgoingEdge(v2real);
            v2real.addIncomingEdge(v1real);
            edgeMap.put(newEdge, newEdge);
            return newEdge;
        }
    }



Начинаю с завистью смотреть на Scala. Генерики в ней - шикарны.
...
Рейтинг: 0 / 0
19.09.2020, 23:01
| Ответить | Цитировать | Написать  
Четверговый архивариус
    #40000702
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Теперь прочувствовали, почему я предпочитаю низким средствам свой ML?
...
Рейтинг: 0 / 0
20.09.2020, 22:56
| Ответить | Цитировать | Написать  
Четверговый архивариус
    #40000708
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я всю жизсть мечтал чтоб "нажал на кнопу" и все задачи из бэклога делались сами.



К сожалению на ниве ИИ ничего подобного так и не было создано ни в ML, нив Haskell ни в Prolog.
Формальная логика не раздупляет то что хочет кастомер.

Так что тут ни в Java и не в С++ дело...
...
Рейтинг: 0 / 0
20.09.2020, 23:25
| Ответить | Цитировать | Написать  
Четверговый архивариус
    #40010012
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
exp98
..... На этой странице я взял паузу ...

---------------------------------------------------------------
Вчера совпала возможность с желанием потрудиться.
Подвинем графы для Графа. Возвращусь к старой теме. Сканирование фотографий. Страница 9 топика была последней в мае месяце.

Немного продвинулся. В качестве кратенькго отчёта кажу 2 "фотосессии".Они не вместились в 1 архив. Приложу 2 архива. Почему 2? Было несколько исходников. Я взял 2 файла "album-01-scaled" и "box-06". создал "фото-отчёты" по принципу 1 исходник <==> "фото-отчёт для 1 исходника.
В основном рассчитываю, что из названий картинок будет понятно, как предлагается резать исходный лист.
---------------------------------------------------------------

Идея отчёта такая.
- Есть лист из альбома, на нём 2 столбца разнокалиберных фотографий.
В отчёте это файл с суффиксом *-full.png
- Программа автоматически разделяет лист на 2 поолвинки: левую и правую. В названиях файлов суффикс *-left либо -right.
- На каждой половинке и в полном файле методом Радона Хаффа рисуются прямые. Параметром взято 30 штук прямых с наименьшим наклоном. Получаются пучки прямых. Они в файлах с названием "-haughLines". Видно, что на -full много ложных прямых. Разбиение по вертикали помогает отсеять много ложных. Это виднопо пучкам на левом и правом соответственно.
- Затем в каждой половине (на основе 3-х версий кластеризации)
- Пучки кластеризуются. В результате предлагается по одной прямой для каждого разреза. Это видно на файлах с названием -cluster.

Это всего лишь предмакет, который надо допиливать на разные случаи жизни. Либо пойти совсем другим путём. В общем я хотел эитм всем сказать, что задачу вполне можно дотянуть. Но увы, на это нужно время. Не знаю когда появится возможность продолжить.

На вопросы отвечу в течение неск дней, тоже если получится.
...
Рейтинг: 0 / 0
19.10.2020, 21:58
| Ответить | Цитировать | Написать  
Четверговый архивариус
    #40010013
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Слеующая отчётик
...
Рейтинг: 0 / 0
19.10.2020, 22:00
| Ответить | Цитировать | Написать  
Четверговый архивариус
    #40010023
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Посмотрел. Метод столбцов не подходит.

Вот альбом детских фоток. Видно что конфигурация рамок на сканах может быть совершенно любой.
Даже не 4х4. И не 2х2. А есть еще лесенка. Зигзаг. И вообще безо всякого направления. Веером.
Как игральные карты.
...
Рейтинг: 0 / 0
19.10.2020, 23:01
| Ответить | Цитировать | Написать  
Четверговый архивариус
    #40010228
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Веер, зигзаг и т.п. кладутся ручками в отдельные каталоги как параметр особых алгоритмов.
Я не настолько широко образован, чтобы быть в курсе всех современных решений.
Веер - уже упоминалось: нужно искать паттерн верхнего уголка, если таковой имеется. Ну а вдруг в фото на стенке висит портрет, а в нём на стенке висит портрет ...
...
Рейтинг: 0 / 0
20.10.2020, 17:10
| Ответить | Цитировать | Написать  
15 сообщений из 540, страница 22 из 22
  22  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Четверговый архивариус
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=40000588&tid=1339720]:
 0ms
get settings:
 8ms
get forum list:
 13ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 153ms
get topic data:
 10ms
get forum data:
 3ms
get page messages:
 45ms
get tp. blocked users:
 1ms
others: 238ms
total:  477ms
созд. / загр.: 477ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]