2016-03-23

Построение дерева цифрового поиска

Ниже приведена иллюстрация построения дерева цифрового поиска на Python (см. алгоритм в посте http://blog.coolsoftware.ru/2016/03/blog-post.html):

f = open("f1.txt")
lines = f.read().split()
f.close()
 
def sort(array):
    equal = []
    greater = []
    less = []
    if len(array) <= 1:
        return array
    linem = array[int((len(array)-1)/2)]
    for line in array:
        if linem < line:
            greater.append(line)
        elif linem > line:
            less.append(line)
        elif linem == line:
            equal.append(line)
    return sort(less) + equal + sort(greater)
 
sorted_lines = sort(lines) 
print(sorted_lines)
 
def node(C, P):
    print(P + C)
    return P + " "
 
def R(P, K, I0, J0):
    I = I0
    Si = sorted_lines[I]
    Li = len(Si)
    if K >= Li and I == J0:
        return
    if K < Li:
        C = Si[K]
    else:
        C = "{0}"
    X = node(C, P)
    J = I
    while True:
        if J == J0 or sorted_lines[J+1][K] != C:
            R(X, K+1, I, J)
            if J == J0:
                break
            I = J + 1
            Si = sorted_lines[I]
            Li = len(Si)
            C = Si[K]
            X = node(C, P)
        J = J + 1
 
N = len(sorted_lines)
X = node("[ROOT_NODE]", "")
R(X, 0, 0, N-1)

f1.txt:

BC
ABBA
ABC
ABA
ABB
BAC
A

Вывод:

['A', 'ABA', 'ABB', 'ABBA', 'ABC', 'BAC', 'BC']
[ROOT_NODE]
 A
  {0}
  B
   A
   B
    {0}
    A
   C
 B
  A
   C
  C

===
Перепечатка материалов блога разрешается с обязательной ссылкой на blog.coolsoftware.ru

2016-03-16

Поиск подстрок с помощью дерева цифрового поиска

Теория

Задача: имеется два больших (100 000+) списка строк, и требуется отфильтровать первый список (Source List) таким образом, чтобы в нем остались только строки, содержащие подстроки из второго списка (Search List).

Решать эту задачу будем следующим образом: для каждой строки Z из Source List будем искать строку S из Search List, такую, что S является подстрокой Z.

Примитивный алгоритм

Можно решить задачу нахождения подстроки из списка Search List при помощи следующего очевидного (примитивного), но крайне медленного алгоритма: будем последовательно перебирать все строки S из Search List до тех пор, пока не окажется, что S является подстрокой Z. При этом, алгоритм поиска подстроки в строке можно использовать либо примитивный, либо один из более продвинутых (например, Бойера-Мура, см. https://ru.wikipedia.org/wiki/Поиск_подстроки). Однако, использование более быстрого алгоритма поиска подстроки в строке не сильно ускоряет поиск подстроки из списка, т.к. все-равно требуется перебрать в среднем N/2 строк (здесь N - количество строк в Search List).

Дерево цифрового поиска

Дерево цифрового поиска (также бор, Trie, Префиксное дерево) - структура данных, которая используется для осуществления поразрядного поиска. Каждый узел дерева содержит значение одного “разряда” (в нашем случае - строковый символ). Вся строка представлена последовательностью узлов от корня до листа дерева. Пример - дерево цифрового поиска для строк A, ABA, ABB, ABBA, ABC, BAC, BC:

    [ROOT NODE]
    /         \
   A           B
  / \         / \
{0}  B       A   C
   / | \    /
  A  B  C  C
    / \
  {0}  A

Почитать про эту структуру можно, например, тут: https://en.wikipedia.org/wiki/Trie.

Алгоритм A1 поиска префикса строки S по дереву:

1. Пусть L = длина строки S.
2. Если L = 0 (“пустая” строка), то выход: префикс не найден.
3. Если дерево не содержит узлов (“пустое” дерево), то выход: префикс не найден.
4. Терминальный узел T = NULL.
5. Текущий узел P = корень дерева ( [ROOT NODE] ).
6. Цикл по K = 1..L:
7. Если у текущего узла нет дочернего, соответствующего символу S[K], то выход из цикла.
8. Текущий узел P = дочерний, узел, соответствующий символу S[K].
9. Если у узла P есть дочерний узел с терминальным символом {0}, то присваиваем его T.
10. Конец цикла.
11. Если узел P - лист, то выход: префикс найден.
12. Если T не равно NULL, то выход: префикс найден.
13. Префикс не найден.

В качестве терминального символа {0} как правило используется символ NUL с ASCII-кодом 0, который не может встретиться в строке.

Алгоритм A2 поиска подстроки строки S по дереву.

1. Пусть L = длина строки S.
2. Если L = 0 (“пустая” строка), то выход: подстрока не найдена.
3. Если дерево не содержит узлов (“пустое” дерево), то выход: подстрока не найдена.
4. Цикл по K = 1..L:
5. Пусть Sk - суффикс строки S, начиная с K-го символа (суффикс длины L-K+1).
6. Используем алгоритм A1 для поиска префикса строки Sk по дереву; если префикс найден, то выход: подстрока найдена.
7. Конец цикла.
8. Подстрока не найдена.

В алгоритмах A1 и A2 использованы определения префикса и суффикса строки из статьи: https://ru.wikipedia.org/wiki/Подстрока. По-простому: префикс строки длины X - это первые X символов строки, суффикс строки длины Y - последние Y символов строки.

Построение дерева цифрового поиска

Обозначения:

N - количество строк.
Si - i-я строка, i = 1..N.
Li - длина i-ой строки.
[ROOT NODE] - корневой узел.

Построение дерева цифрового поиска:

1. Сортировка списка строк по возрастанию, удаление дубликатов.
2. Вызов рекурсивной процедуры R( [ROOT NODE], 1, 1, N).

Рекурсивная процедура R (параметры: P - узел-родитель, K - позиция текущего символа, I0, J0 - индексы строк; I0<=J0):

1. Индекс i = I0.
2. Если K > Li и i = J0, то выход из процедуры R.
3. Если K <= Li, то символ C = Si[K], иначе C = {0}.
4. Создать X = узел (C, P).
5. Индекс j = i.
6. Цикл:
7. Если j = J0 или S(j+1)[K] не равно C, то:
8. Вызвать R (X, K+1, i, j)
9. Если j = J0, то выход из цикла.
10. i = j+1.
10. C = Si[K].
11. Создать X = узел (C, P).
12. Конец если.
13. j = j + 1.
14. Конец цикла.

См. иллюстрацию на Python: http://blog.coolsoftware.ru/2016/03/blog-post_23.html.

Оптимизация (сжатие)

Под-деревья, узлы которых содержат не более одного потомка, можно объединить в один узел - см. узел (AC) в примере ниже.

    [ROOT NODE]
    /         \
   A           B
  / \         / \
{0}  B      (AC) C
   / | \
  A  B  C
    / \
  {0}  A

Реализация на Delphi: https://github.com/optinsoft/SearchStrings

===
Перепечатка материалов блога разрешается с обязательной ссылкой на blog.coolsoftware.ru

2016-03-01

Lazarus Exe

Чтобы уменьшить размер генерируемого Lazarus exe файла, нужно включить следующие опции в параметрах компилятора:

“Компиляция и компоновка”->”Стиль модулей”->”Умная компоновка (-CX)”
“Компиляция и компоновка”->”Компоновка”->”Умная компоновка (-XX)”
“Отладка”->”Информация для GDB”->”Использовать внешний файл отладочных символов GDB (-Xg)”
“Отладка”->”Прочая отладочная информация”->”Вырезать символы из исполнимого файла (-Xs)”

===
Перепечатка материалов блога разрешается с обязательной ссылкой на blog.coolsoftware.ru

2016-02-18

ASUS N10 Nano vs TP-LINK TL-WN823N

Решил сравнить скорость двух беспроводных сетевых USB-адаптеров: ASUS N10 Nano и TP-LINK TL-WN823N. На первом написно до 150 Mbps, на втором - до 300 Mbps.

Оба адаптера втыкались в Raspberry Pi B+. Для тестов использовался iperf.

Результаты тестов представлены на Рис. 1,2. Как видим, ASUS показывает скорость около 42 Mbit/sec, TP-LINK - около 74 Mbit/sec.

Рис.1. ASUS N10 Nano.

Рис.2. TP-LINK TL-WN823N.

===
Перепечатка материалов блога разрешается с обязательной ссылкой на blog.coolsoftware.ru

2015-12-14

Обновить иконки рабочего стола (Windows)

Заметка себе на память:

ie4uinit.exe -ClearIconCache

===
Перепечатка материалов блога разрешается с обязательной ссылкой на blog.coolsoftware.ru

2015-06-05

Teredo ipv6

Настройка ipv6 (Teredo):

Мой компьютер (контекстное меню) –> Управление -> Службы (Рис. 1):
Вспомогательная служба IP –> Тип запуска –> Выбираем из списка: Автоматически
Пуск –> Выполнить –> regedit
В реестре по адресу
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\services\Dnscache\Parameters
создать ключ AddrConfigControl типа DWORD со значением 0 (Рис. 2).
Пуск –> Панель управления –> Сеть и Интернет –> Сетевые подключения –> Подключение по локальной сети –> Свойства (Рис. 3):
Протокол Интернета версии 6 (TCP/IPv6) –> включить и в Свойствах указать:
Использовать следующие адреса DNS-серверов:
Предпочитаемый DNS-сервер: 2001:4860:4860::8888
Альтернативный DNS-сервер: 2001:4860:4860::8844
Пуск –> Выполнить –> gpedit.msc
Конфигурация компьютера –> Административные шаблоны –> Сеть –> Параметры TCP/IP –> Технологии Туннелирования IPv6 (Рис. 4):
Классификация Teredo по умолчанию –> Включить –> Включенное состояние
Частота обновления Teredo –> Включить –> 10
Состояние Teredo –> Включить –> Корпоративный клиент
Порт клиента Teredo -> Не задано
Имя сервера Teredo –> Включить –> Выбираем из списка: teredo.remlab.net
Пуск – Выполнить – cmd:
netsh int ipv6 delete route ::/0 Teredo
netsh int ipv6 add route ::/0 Teredo
Тестирование подключения: http://test-ipv6.com/

Рис. 1

Рис. 2

Рис.3

Рис. 4

Стянул отсюда: http://blog.cherepovets.ru/serovds/2011/11/15/teredo-win7/

===
Перепечатка материалов блога разрешается с обязательной ссылкой на blog.coolsoftware.ru

2015-03-20

Raspberry Pi

Полезные ссылки, касающиеся разработки под Raspberry Pi. Пишу главным образом для себя, чтобы не забыть :) Пост будет время от времени дополнятся (я надеюсь :)

1. Кросс-компиляция Qt 5 для Raspberry Pi:

http://qt-project.org/wiki/RaspberryPi_Beginners_guide

Несколько замечаний:

a) git clone git://gitorious.org/qt/qt5.git не работает, вместо него нужно выполнять: git clone http://git.gitorious.org/qt/qt5.git

б) сперва лучше (imho) залить образ на флешку ( sudo dd bs=1M if=2015-02-16-raspbian-wheezy.img of=/dev/sdb ), вставить флешку в Raspberry Pi, установить апдейты и библиотеки (например, для разработки под X11: http://doc.qt.io/qt-5/linux-requirements.html), потом сделать образ этой флешки ( sudo dd bs=1M if=/dev/sdb of=rasp-pi.img ) и уже с ним работать дальше.

в) “Магическое” число 62914560 (
sudo mount -o loop,offset=62914560 rasp-pi.img /mnt/rasp-pi-rootfs ) можно вычислить следующим образом:

[vitaly@localhost opt]$ sudo fdisk -l rasp-pi.img

Disk rasp-pi.img: 7892 MB, 7892631552 bytes, 15415296 sectors
Units = sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 512 bytes
I/O size (minimum/optimal): 512 bytes / 512 bytes
Disk label type: dos
Disk identifier: 0x0009bf4f

Устр-во Загр     Начало       Конец       Блоки   Id Система
rasp-pi.img1            8192      122879       57344    c W95 FAT32 (LBA)
rasp-pi.img2          122880     6399999     3138560   83 Linux

122880 - это начало раздела (номер первого сектора раздела), который нужно подмонтировать. 122880 * 512 = 62914560.

2.”Нативная” компиляция Qt5 на Raspberry Pi.

http://qt-project.org/wiki/Native_Build_of_Qt5_on_a_Raspberry_Pi

Я не пробовал. Утверждается, что идет очень долго.

3. Кросс-компиляция Wt на Raspberry Pi:

http://redmine.emweb.be/projects/wt/wiki/Cross_compile_Wt_on_Raspberry_Pi

4. “Экономичная реализация графического интерфейса пользователя на базе одноплатного компьютера Raspberry Pi” (“Автоматика и программная инженерия”, 2014, №2(8))

http://www.nips.ru/images/stories/zhournal-AIPI/10/aipi-2-2014-3.pdf

Хорошее подробное описание настройки кросс-компиляции.

===
Перепечатка материалов блога разрешается с обязательной ссылкой на blog.coolsoftware.ru

2014-11-29

Throttling

Троттлинг (throttling) - это регулирование (ограничение) скорости какого-нибудь процесса. Например, bandwidth throttling - регулирование пропускной способности канала (обычно измеряется в килобайтах в секунду, kB/s).

В листинге ниже показано, как можно реализовать троттлинг.

for (int i = 0; i < 1000; i++)
{
    while (!throttle_acquire()); //цикл ожидания
    doWork(); //выпоняем работу
}

В этом примере процесс состоит из 1000 итераций. Каждая итерация заключается в вызове функции doWork(), которая, например, отправляет очередную порцию данных. Ограничение скорости заключается в введении лимита на количество этих вызовов N за период времени dT. Перед вызовом doWork() осуществляется проверка превышения лимита: функция throttle_acquire() возвращает false, если лимит превышен, и true, в противном случае.

Троттлинг можно реализовать с использованием кольцевого буфера. Этот кольцевой буфер заполняется моментами времени последних вызовов функции doWork() (см пример выше). Размер буфера равен максимально разрешенному количеству этих вызовов N за период времени dT. Если буфер полностью заполнен, то функция acquire() возвращает false. Это означает, что необходимо подождать, пока из буфера не будет удален хотя бы один момент времени, который располагается от текущего момента (“сейчас”) дальше, чем dT.

Реализацию троттлинга на C++ (throttle.h) я выложил на github: https://github.com/coolsoftware/Throttle.

Пример использования класса throttle можно посмотреть в TestThrottle.cpp.

===
Перепечатка материалов блога разрешается с обязательной ссылкой на blog.coolsoftware.ru

2014-11-27

Сборка zlib в Visual Studio 2010

1. Скачиваем zlib 1.2.8 с http://www.zlib.net/
2. Распаковываем архив в c:\zlib-1.2.8
3. Открываем в Visual Studio 2010 проект C:\zlib-1.2.8\contrib\vstudio\vc10\zlibvc.sln
4. Меняем следующие настройки проекта zlibstat:

Конфигурация Debug:

General->Output Directory: **..\..\..\win32-MDd\**
General->Intermediate Directory: **..\..\..\win32-MDd\Tmp\**
C/C++->Preprocessor->Preprocessor Definitions: <удаляем **ZLIB_WINAPI**>
C/C++->Code Generation->Runtime Library: Multi-threaded Debug DLL (/MDd)
Librarian->General->Output File: $(OutDir)\..\zlibMDd.lib

Конфигурация Release:

General->Output Directory: **..\..\..\win32-MT\**
General->Intermediate Directory: **..\..\..\win32-MT\Tmp\**
C/C++->Preprocessor->Preprocessor Definitions: <удаляем **ZLIB_WINAPI**>
C/C++->Code Generation->Runtime Library: Multi-threaded (/MT)
Librarian->General->Output File: $(OutDir)\..\zlibMT.lib

5. Собираем Debug и Release версии zlibstat. На выходе получаем:

C:\zlib-1.2.8\zlibMDd.lib
C:\zlib-1.2.8\zlibMT.lib

6. Открываем в Visual Studio 2010 любой проект C++ и открываем Property Manager->(Project Name)->Debug | Win32->Microsoft.Cpp.Win32.user->Common Properties->VC++ Directories. Добавляем c:\zlib-1.2.8 в Include Directories, Library Direcories и Source Directories.

===
Перепечатка материалов блога разрешается с обязательной ссылкой на blog.coolsoftware.ru

2014-05-29

Генерация пар открытых/закрытых ключей (RSA) на C#

Понадобилось мне создать пару открытый/закрытый ключ на C#. Я поискал немного и нашел замечательную криптографическую библиотеку под названием Bouncy Castle: https://www.bouncycastle.org/. Для C# исходники можно скачать здесь: http://www.bouncycastle.org/csharp/. Ниже описан порядок установки и использования.

Качаем bccrypto-net-1.7-src.zip, распаковываем в какой-нибудь каталог на диске.
Открываем проект csharp.sln в Visual Studio 2010.
В свойствах проекта crypto в Build->General->Conditional compilation symbols комментируем INCLUDE_IDEA.
Пробуем выполнить Build и видим ошибки:
error CS1504: Source file ‘C:\temp\csharp\crypto\src\crypto\engines\IDEAEngine.cs’ could not be opened (‘Неопознанная ошибка ‘)
error CS1504: Source file ‘C:\temp\csharp\crypto\test\src\crypto\test\IDEATest.cs’ could not be opened (‘Неопознанная ошибка ‘)
error CS1504: Source file ‘C:\temp\csharp\crypto\src\asn1\misc\IDEACBCPar.cs’ could not be opened (‘Неопознанная ошибка ‘)
Удаляем из проекта crypto отсутствующие файлы:
src\crypto\engines\IDEAEngine.cs
src\asn1\misc\IDEACBCPar.cs
test\src\crypto\test\IDEATest.cs
Пробуем еще раз выполнить Build - на этот раз все должно получиться и будет создана библиотека crypto.dll.
Прописываем созданную библиотеку в References проекта.

Код для генерации пары открытый/закрытый ключ приведен ниже. Открытый ключ - в формате PKCS#8. Закрытый ключ - в формате PKCS#1.

using Org.BouncyCastle.Asn1.Pkcs;
using Org.BouncyCastle.Asn1.X509;
using Org.BouncyCastle.Crypto;
using Org.BouncyCastle.Crypto.Parameters;
using Org.BouncyCastle.Pkcs;
using Org.BouncyCastle.Security;
using Org.BouncyCastle.X509;
using Org.BouncyCastle.Crypto.Generators;
 
RsaKeyPairGenerator rsa = new RsaKeyPairGenerator();
rsa.Init(new KeyGenerationParameters(new Org.BouncyCastle.Security.SecureRandom(), 1024));
AsymmetricCipherKeyPair pair = rsa.GenerateKeyPair();
PrivateKeyInfo privateKeyInfo = PrivateKeyInfoFactory.CreatePrivateKeyInfo(pair.Private);
byte[] serializedPrivateBytes = privateKeyInfo.PrivateKey.ToAsn1Object().GetDerEncoded();
string privateKey = Convert.ToBase64String(serializedPrivateBytes);
SubjectPublicKeyInfo publicKeyInfo = SubjectPublicKeyInfoFactory.CreateSubjectPublicKeyInfo(pair.Public);
byte[] serializedPublicBytes = publicKeyInfo.ToAsn1Object().GetDerEncoded();
string publicKey = Convert.ToBase64String(serializedPublicBytes);

===
Перепечатка материалов блога разрешается с обязательной ссылкой на blog.coolsoftware.ru