Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.67/3: Рейтинг темы: голосов - 3, средняя оценка - 4.67
 Аватар для belalugoci
475 / 294 / 29
Регистрация: 01.06.2018
Сообщений: 3,676

Поиск "рисунка" бит во входном файле

19.02.2019, 12:18. Показов 634. Ответов 3
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Те кто в курсе помнят какой фигнёй я сейчас занят. В продолжение работы с битами появилась идея сделать программу, которая сканирует указанный файл и все последовательные 512 байт объединяет в матрицу 64х64 бита. В такой матрице требуется найти определенные рисунки, например такие
0010
1000
0001
0100
причем значащими для поиска являются только 1 и нули в "зеркальных" позициях, то есть
0100
0001
1000
0010
своеобразное колечко с определенными позициями 1 и 0. Черные позиции битов могут иметь любое значение и игнорируются.
Так как в 64х64 таких "колечек" может быть уйма в одной матрице, то нужно считать их количество и в выходной файл писать статистику, например шестнадцатиричное смещение в файле матрицы (адрес 512-байтного блока) и перечень таких вот аномалий с количеством. Например вот в таком виде:
Code
1
0x00000000, 0x00, 5, 0x01, 2
то есть в блоке со смещением 0х00000000 было найдено два рисунка, первый 0х00 встречается 5 раз, в второй 0х01 два раза.

В целом интересны рекомендации по тому, как организовать отображение этих рисунков. чтобы при необходимости можно было легко добавлять новые. Причем рисунок может быть разной формы и состоять из разного числа бит. На данный момент есть небольшие из 4 и 6 бит.
Мои предложения:
1) Держать битовую маску и накладывать её на разные позиции:
++ вероятно быстрые операции над битами
-- представление маски разноразмерной матрицей
2) Массивы относительных координат значащих 1 и 0
++ простота добавления новых
-- наверное операции с BitArray
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
19.02.2019, 12:18
Ответы с готовыми решениями:

Удвоить все пробелы во входном файле, в конце дописать строку «Количество пробелов во входном файле: х»
У меня есть вот такой код, только в этом коде с файла in в out переносится ввесть текст и пробелы заменяет на нули и считает их. Мне...

Поиск анаграмм во входном файле
Условие. В заданном алфавите слов найти все анаграммы. Входные данные. Есть файл "input.txt" в нем список слов. Выходные...

Задача Pascal ABC. Во входном файле дан массив А и массив из элементов которых будет осуществляться поиск в массиве А
Во входном файле дан массив А и массив из элементов которых будет осуществляться поиск в массиве А. Изменить массив А таким образом, чтобы...

3
 Аватар для belalugoci
475 / 294 / 29
Регистрация: 01.06.2018
Сообщений: 3,676
21.02.2019, 08:17  [ТС]
В общем сделал первый вариант. Кому интересно могут подсказать как и что можно сделать лучше или иначе.
Кроме кода в сообщении прикладываю сам проект. В теле указываете путь к существующему файлу для сканирования. Используется сторонний модуль для рисования прогресса выполнения, кому не нравится могут легко его вырезать совсем. Файлы размером 10-20 мегабайт на моём ПК сканируются за 30 секунд, так что гигабайтные файлы этому коду не скармливайте. Чтение с диска идёт блоками по 512 байт (4096 бит = 64х64), операции по поиску проверяют каждый бит отдельно.
Так же в архиве с проектом есть файл test2.txt размером в 512 байт и готовым шаблоном для проверки, результат работы программы должен давать 1 блок и 1 совпадение.

Основной код:
C#
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Threading;
 
namespace Matrix64
{
    class Program
    {
        static byte[] buf = new byte[512]; // буфер для файла
        static int blocksCount = 0; // всего блоков в файле (кратно 512)
        static int comparedCount = 0; // общее число совпадений с шаблоном
        static int maxCount = 0; // максимальное число совпадений для одного блока
        static int emptyCount = 0; // число блоков, где нет совпадений совсем
        
        // шаблон для поиска с относительными координатами от левого верхнего угла и значением бита {X, Y, BIT}
        static int[,] XY = { {1, 0, 0}, {2, 0, 1}, {0, 1, 1}, {3, 1, 0}, {0, 2, 0}, {3, 2, 1}, {1, 3, 1}, {2, 3, 0} };
 
        static void Main(string[] args)
        {
            string filePath = @"c:\drivers\temp\bits.7z"; // путь к файлу
            Console.WriteLine("Чтение из файла " + filePath);
 
            // конструктор ProgressBar немного переделал, есть возможность настраивать длину полосы, отображение процентов и анимации
            using (var progress = new ProgressBar(50, true)) // можно убрать если нет желания смотреть на полосу прогресса
            using (var infile = File.OpenRead(filePath))
            {
                while (true)
                {
 
                    progress.Report((double)blocksCount / (infile.Length / 512)); // можно убрать если нет желания смотреть на полосу прогресса
                    var bytesRead = ReadBlock(infile, buf);
                    if (bytesRead == 0)
                        break;
                    int tempMaxCount = 0;
                    for (int x = 0; x < 60; x++) // по идее вместо 60 должна стоять формула для подсчета ширины мартицы согласно проверяемому шаблону
                        for (int y = 0; y < 60; y++)
                            if (SearchIcon(x, y, XY))
                            {
                                comparedCount++;
                                tempMaxCount++;
                            }
                    if (tempMaxCount == 0) emptyCount++;
                    if (tempMaxCount > maxCount) maxCount = tempMaxCount;
                    blocksCount++;
                    //Thread.Sleep(1);
                }
            }
            Console.WriteLine("Done.");
            Console.WriteLine("Совпадений: {0}", comparedCount);
            Console.WriteLine("Всего блоков: {0} / Блоков без аномалий: {1} ({2}%)", blocksCount, emptyCount, emptyCount * 100 / blocksCount);
            Console.WriteLine("Совпадений на блок (среднее): {0}", comparedCount / blocksCount);
            Console.WriteLine("Совпадений на блок (макс): {0}", maxCount);
            Console.ReadKey();
        }
 
        // проверка всех битов из массива шаблона
        static bool SearchIcon(int x, int y, int[,] xy)
        {
            for (int pos = 0; pos < xy.Length / 3; pos++)
                if (!IsSet(x + xy[pos, 0], y + xy[pos, 1], xy[pos, 2])) return false;
            return true;
        }
 
        // проверка одного бита согласно координатам в матрице
        static bool IsSet(int x, int y, int bit)
        {
            return ((buf[y * 8 + x / 8] & (int)Math.Pow(2, 7 - (x < 8 ? x : x % 8))) == 0 ? 0 : 1) == bit ? true : false;
        }
 
        // стырено откуда-то, читает блоками файл
        static int ReadBlock(Stream s, byte[] block)
        {
            int position = 0;
            while (position < block.Length)
            {
                var actuallyRead = s.Read(block, position, block.Length - position);
                if (actuallyRead == 0)
                    break;
                position += actuallyRead;
            }
            return position;
        }
    }
}
ProgressBar.cs
C#
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
using System;
using System.Text;
using System.Threading;
 
/// <summary>
/// An ASCII progress bar
/// </summary>
public class ProgressBar : IDisposable, IProgress<double> {
    private int blockCount = 30;
    private bool spercent = false;
    private bool sanimation = false;
    private readonly TimeSpan animationInterval = TimeSpan.FromSeconds(1.0 / 8);
    private const string animation = @"|/-\";
 
    private readonly Timer timer;
 
    private double currentProgress = 0;
    private string currentText = string.Empty;
    private bool disposed = false;
    private int animationIndex = 0;
 
    public ProgressBar(int _blkCount, bool _percent = false, bool _sanimation = false) {
        timer = new Timer(TimerHandler);
        blockCount = _blkCount;
        spercent = _percent;
        sanimation = _sanimation;
        // A progress bar is only for temporary display in a console window.
        // If the console output is redirected to a file, draw nothing.
        // Otherwise, we'll end up with a lot of garbage in the target file.
        if (!Console.IsOutputRedirected) {
            ResetTimer();
        }
    }
 
    public void Report(double value) {
        // Make sure value is in [0..1] range
        value = Math.Max(0, Math.Min(1, value));
        Interlocked.Exchange(ref currentProgress, value);
    }
 
    private void TimerHandler(object state) {
        lock (timer) {
            if (disposed) return;
 
            int progressBlockCount = (int) (currentProgress * blockCount);
            int percent = (int) (currentProgress * 100);
            string text;
            if (sanimation)
                text = spercent ? string.Format("[{0}{1}] {2,3}% {3}", new string('#', progressBlockCount), new string('.', blockCount - progressBlockCount), percent, animation[animationIndex++ % animation.Length]) :
                                        string.Format("[{0}{1}] {2}", new string('#', progressBlockCount), new string('.', blockCount - progressBlockCount), animation[animationIndex++ % animation.Length]);
            else
                text = spercent ? string.Format("[{0}{1}] {2,3}%", new string('#', progressBlockCount), new string('.', blockCount - progressBlockCount), percent) :
                                        string.Format("[{0}{1}]", new string('#', progressBlockCount), new string('.', blockCount - progressBlockCount));
            /*string text = string.Format("[{0}{1}] {2,3}% {3}",
                new string('#', progressBlockCount), new string('.', blockCount - progressBlockCount),
                percent,
                animation[animationIndex++ % animation.Length]);*/
            UpdateText(text);
 
            ResetTimer();
        }
    }
 
    private void UpdateText(string text) {
        // Get length of common portion
        int commonPrefixLength = 0;
        int commonLength = Math.Min(currentText.Length, text.Length);
        while (commonPrefixLength < commonLength && text[commonPrefixLength] == currentText[commonPrefixLength]) {
            commonPrefixLength++;
        }
 
        // Backtrack to the first differing character
        StringBuilder outputBuilder = new StringBuilder();
        outputBuilder.Append('\b', currentText.Length - commonPrefixLength);
 
        // Output new suffix
        outputBuilder.Append(text.Substring(commonPrefixLength));
 
        // If the new text is shorter than the old one: delete overlapping characters
        int overlapCount = currentText.Length - text.Length;
        if (overlapCount > 0) {
            outputBuilder.Append(' ', overlapCount);
            outputBuilder.Append('\b', overlapCount);
        }
 
        Console.Write(outputBuilder);
        currentText = text;
    }
 
    private void ResetTimer() {
        timer.Change(animationInterval, TimeSpan.FromMilliseconds(-1));
    }
 
    public void Dispose() {
        lock (timer) {
            disposed = true;
            UpdateText(string.Empty);
        }
    }
 
}
Вложения
Тип файла: 7z Matrix64.7z (47.2 Кб, 0 просмотров)
0
 Аватар для belalugoci
475 / 294 / 29
Регистрация: 01.06.2018
Сообщений: 3,676
21.02.2019, 12:39  [ТС]
Небольшие изменения. Добавил For() для многопроцессорности, косметические изменения - для ProgressBar добавил отображение размера файла, в конце показывается время выполнения.

Ещё было бы интересно сделать отображение времени оставшегося до конца работы. Интересует не просто деление на отрезки, а именно регулярный расчет, например начиная с 10-го блока. Чтобы было похоже на то, как отображается такое время например в FAR при копировании.
Вложения
Тип файла: 7z Matrix64multicore.7z (131.6 Кб, 1 просмотров)
0
 Аватар для belalugoci
475 / 294 / 29
Регистрация: 01.06.2018
Сообщений: 3,676
21.02.2019, 13:28  [ТС]
Цитата Сообщение от belalugoci Посмотреть сообщение
Code
1
2
3
4
0010
1000
0001
0100
вот еще посетила мысль, а если вместо координатного сравнения каждого бита эти самые биты просто читать и считать по ним хэш. Так как у шаблона тоже будет хэш, то в конце нужно лишь сделать выборку всех хэшей совпадающих с шаблонным.
Хэшем может быть последовательность бит, например для рисунка выше 8 бит дают 1 байт и как раз байты потом и сравнивать, точнее группировать. Число элементов в группе и будет искомым значением.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
21.02.2019, 13:28
Помогаю со студенческими работами здесь

Русский язык в входном файле
Как сделать так, чтобы во входном файле после компиляции язык оставался русским и во входной файл данные заносились на русском языке. C++. ...

RESOURCE_LIMIT - Во входном файле недопустимый символ 0
С помощью команды show parameter pfile посмотрел имя файл инициализационных параметров. Хотел изменить этот файл, добавит туда параметер...

Если во входном файле 69, то в выходной выводит f(66)
если в file.in записано 69 то в file.out записывается f с номером 66, скажите в чём может быть ошибка format PE CONSOLE 4.0 include...

Во входном файле подсчитать количество символов
Здраствуйте, подскажите пожалуйста как в си во входном файле подсчитать количество символов

Во входном файле записано сначала число N
Во входном файле записано сначала число N(1&lt;=N&lt;=100),a затем N моментов времен.Каждый момент времени задается 3 целыми числами-часы,минуты...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Новые блоги и статьи
Оттенки серого
Argus19 18.03.2026
Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .
SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++
8Observer8 17.03.2026
Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip
Символические и жёсткие ссылки в Linux.
algri14 15.03.2026
Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора
ФедосеевПавел 14.03.2026
Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .
делаю науч статью по влиянию грибов на сукцессию
anaschu 13.03.2026
прикрепляю статью
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++
8Observer8 10.03.2026
Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE
8Observer8 10.03.2026
Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки
Neotwalker 08.03.2026
Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru