Доброе всем времечко!

Речь идет об алгоритме обнаружения(обработки, точнее) горячих клавиш. А ещё точнее - их последовательности. Вот, например есть процедура, которой передаётся 1 параметр-ASCII код. ну и при достижении определенных ключевых клавосочетаний чё-то выполняет.
Так вот, хотелось бы узнать о различных реализациях, мотодах для решения этой задачи. Может ссылки, может ищо чё. Естественно упор делается на большую скорость, малый объем памяти и бесконечное(ну большое) ветвление.

Заранее благодарен. --==PPS==--

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

Про различные методики я мало что знаю, но делал примерно так:

- ASCII код помещаем в FIFO буфер (размер - максимально возможная последовательность);

- содержимое буфера проверяем на предмет совпадения с данными в таком примерно массивчике:

db 'a','b','c','d','f','g',0,0 ; последовательность клавиш
dd abcdfg_handler

db 'a','c','d','b',0,0,0,0
dd acdb_handler

dd 0 ; данных больше нет
........

- если есть совпадение, то вызываем соответствующий обработчик.


Поиск выполнять можно быстро, если сравнивать не по-символьно, а сразу по 4 (обычный регистр) или по 8 (mmx).
Размер регистра выбирается в зависимости от максимальной длины ключевой последовательности.

Если ASCII последовательности имеют различную длину (а это скорее всего так и есть), необходимо будет перед сравнением накладывать маску на операнды, что бы сократить количество сравниваетмых символов до необходимого.

Вот примерный код поиска (правда, требует P III, использую в другом месте, но вроде бы и сюда подходит :).

; EAX = длина искомой последовательности.
; ESI - указатель на искомую строку
    neg     al
    add     al,8
    shl     eax,3
    movd    mm0,eax
    pcmpeqd mm1,mm1
    psrlq   mm1,mm0
    movq    mm0,mm1
    pand    mm1,QWORD[ESI]

    mov     ecx, msg_handlers_array ; см. выше
search:
    cmp     DWORD[ECX],0
    jz not_found
    movq    mm2,QWORD[ECX]
    add     ecx,12
    pcmpeqd mm2,mm1
    packssdw mm2,mm2
    movd    eax,mm2
    inc     eax
    jnz     search;
    jmp     DWORD[ecx-4] 

PS
Зачем тему в HEAP поместил.

Спасибо!
Теперь что у меня:

1)
есть связанный список с дочерними элементами (черное дерево, если не ошибаюсь):
2-х сторонняя связь и отдельное поле для дочернего дерева+8 байтное поле для ASCII кода и арес ф-ии, который надо выполнить, если на этом этапе ASCII совпал. Дочерний элемент указывает на новую часть (ступень N-мерного дерева) с новыми клавосочетаниями.

2)
Затем существует двухсторонний связанный список (нет дочерних элементов),каждый элемент которого указывает на текущую позицию в дереве с клавосочетаниями.

Этот способ учитывает вроде бы все требования, но тормоз:
Приходится смотреть все элементы 2-го дерева+для каждого элемента 2-го дерева попасть на ветвь N-мерного дерева и там проверить следующую букву. Короче, легче, конечно на картинке объяснять.

Вариант у S_T_A_S_ , не обработает промежуточные команды, да и там придется запоминать прошлую позицию, для того, чтобы считать каждую букву первой в какой-то строке.
Так, например
1)123Пуск
2)1123Пуск
2-й вариант будет ошибочным, хотя он верный.

При так к примеру клавосочетания типа
BeepOn
BeepOff
BeepModeVolUp
BeepModeVolDown
BeepModeVolOff
BeepMode1
BeepMode2

Вариант простого сравнения строк будет не очень, т.к. надо иметь в памяти посл-ть из последних нажатых символов длиной в длину максибально длинного ключевого слова «BeepModeVolDown», а при использовании деревьев быдет основание «Beep» , дочерний элемент последней буквы будет дерево №1 «On» №2 «Mode» у него на конце – ответвление «VOl». И т.д.

По моему мнению, если усовершенствовать метод простого сравннеия можно придти к этому, и к какому-нить другому.

Так вот и хочется узнать какой-нить по короче, но без недостатков(или с перечисленными приемуществами), и быстрый, и шоб памяти поменьше. Может те же хэш-или ещё какие таблицы… Может код у ког какой есть.

З.Ы. S_T_A_S_, всё выше перечисленной не в укор, а просто очень хочется найти ответ на этот вопрос, и я просто сравнивал. Этот метод, конечно, ввиду использования места в памяти для структур деревьев памяти жрет тоже нефигово. А в Heap это я по ошибке создал. Если «Даос»-у будет угодно, то перенесёт и в другой раздел.

Какие проблемы использовать буфер с длиной равной длине максимально длинного ключевого слова?
Это IMHO упрощает программу - нет необходимости в сложных структурах (сохраним деревья для детей ;), запоминании предыдущих состяний (они уже хранятся в буфере)


Вот вариант №2 (усовершенствовенный)

- клавосочетания делим на группы по количеству символов;

- адреса групп храним в массиве:
........
dd klavasochetanie6
dd klavasochetanie7
dd 0; нет клавосочетаний такой длины

- берём последние N символов из буфера;

- ищем в соответствующей группе, если группа существует;

- 2 предыдущих пункта повторяем для N+1;


На первый взгляд слишком много поисков придётся делать.. вроде бы плохо..
Но макс. длина последовательности - 15 байт.
Это максимум 4 сравнения обычными регистрами, циклы никакие не нужны.
Такое сравнение (в самом худьшем случае) будет быстрее, чем вычисление хэша от строки! (причём в случае с хэшами бинарного поиска всё равно не избежать).
Ещё бы хорошо отсортировать данные в группах по алфавиту -
так можно избежать проверок лишних элементов.
Или сравнивать строки начиная на сначала, а с конца.

Реализация этого на асме довольно проста будет.
Если делать на "Си в стиле Си", то может очень сильно усложниться :(

По поводу размера самих данных. Деревья хранят указатели - а один указатель - это 4 символа.
Тут экономия IMHO обманчива.
Если же размер критичен (последовательностей слишком много), можно применить примитивное сжатие строк - выделить несколько токенов (например "Beep", "Mode") заменить их на 01, 02,... во время инициализации проги "распаковать" данные.


> „Так, например
1)123Пуск
2)1123Пуск
2-й вариант будет ошибочным, хотя он верный. “

Буфер Firs In - First Out. Данные дописываем в конец, при этом смещаем содержимое "влево".
Подстроки нужно брать не от начала буфера, а от (конец_буфера - длина_подстроки).
Тогда проблем никаких нет.


ЗЫ
Если нужно, накидаю примерный код, только напиши на чём лучше.. Я щас подобным занимаюсь, но поиск у меня в текстовых файлах, которые я терпеть не могу =)


ЗЫЫ
В HEAP некоторые не заглядывают, так что возможно поэтому тут нет кучи ссылок на методы реализации :).

Благодарю!

По поводу обманчивости в объеме, то да, это действительно так. И знаешь, действительно, надо бы попробывать написать таким способом. Только вот, на мой взгляд, надо бы чуть усовершенствовать:

;*************************************CODE**************************** ***
KeystrokesArray:
SetBootWW :
db ‘S’ dd 0
db ‘e’ dd 0
db ‘t’ dd 0
db ‘B’ dd 0
db ‘o’ dd 0
db ‘o’ dd 0
db ‘t’ dd Offset WriteBoottVariants
db ‘A’ dd 0
db ‘W’ dd Offset SetBootAfterWindows
SetBootM:
db ‘S’ dd 0
db ‘e’ dd 0
db ‘t’ dd 0
db ‘B’ dd 0
db ‘o’ dd 0
db ‘o’ dd 0
db ‘t’ dd Offset WriteBoottVariants
db ‘M’ dd Offset SetBootManual
SetBootBW:
db ‘S’ dd 0
db ‘e’ dd 0
db ‘t’ dd 0
db ‘B’ dd 0
db ‘o’ dd 0
db ‘o’ dd 0
db ‘t’ dd Offset WriteBoottVariants
db ‘B’ dd 0
db ‘W’ dd Offset SetBootBeforeWindows

WriteBoottVariants Proc
Write (‘
Boot with windows – WW,
Boot before windows – BW,
Boot manual – M,
’);
Ret
WriteBoottVariants EndP
;********************************************************************* ***

Пояснение
Т.е при совпадении уже набранного буфера до «SetBoot», запускается процедура вывода на экран подсказки о дальнейших вариантах. После чего пользователь набирает нужное ему окончание. По достижении этого окончания вызавается соответ-ая ф-я.
Есть тута один недостаток: скока раз повторилось «BootSet»??! Хотя, да, упаковать примитивно действительно – идея. В программе у меня очень много команд именно с таким интерфейсом. И эти повторения я избежал, создав деревья.

Чё та мне стало интересно по поводу объёмов данных.
Давай подсчитаем:

===
_статических_
===

В приведенном выше примере размер структуры: 26*5=130 байт.
При использовании деревьев – 12*5=60 байт.

===
_динамических_
===

В приведенном выше примере размер: так же 130 байт + размер рабочего буфера =9+1.
Итого: 140 байт

Дерево клавиш: (1+4+4+4+(01+04))*12
Дерево текущих направлений: (1+4+4+4)*(до 12, но всреднем - 3) При безошибочном наборе ==2

Суммируем:255.

Превосходство буферного метода – в 1.8 раза меньше места, но это для стольки строк, а если больше, то вопрос спорный. Бесспорное превосходство- это скорость, конечно же больше.

;**********************************1-типная*************************** ******
Рассмотрим однотипную (только про один вид команды, например про ту же загрузку) и 2-х уровневую последовательность команд.

(2-х уровневая означает, что не так: BootGet1,BootGet2,BootGetDate1,BootGetDate2 – это 3-х уровневая., а если добавить BootGetDateWhenSet1, BootGetDateWhenSet2 – это 4-х уровневая)

1)Пусть первый уровень содержит X букв (по 4(для адр ф-й) + «А»(для элемента сравнения, т.к. ASCII – это 1 байт, а код от клавиатуры=SCANCODE+FLAGS=4 байта) байт в каждом)
2)Пусть второй уровень содержит Y букв (4+A).
3)Пусть команд будет С штук.

V – объем в байтах.

Для буферного метода: V(X)=С*[X + Y]*(A+04) + [X+Y+1] (это буффер)

Для метода c деревьями: V(X)= (1+4+4+4+(04+A))*[X + С*Y] + (X+ С*Y)*(3 - всреднем)

;***********************************2-х типная*******************************

Для буферного метода: V(X)=
С1*[X1 + Y1]*(A+04) + С2*[X2 + Y2]*(A+04) + [X+Y+1] (это буффер)


Для метода c деревьями: V(X)=
(1+4+4+4+(04+A))*[X1 + С1*Y1] + (X1+ С1*Y1)*(3 - всреднем)
+
(1+4+4+4+(04+A))*[X2 + С2*Y2] + (X2+ С2*Y2)*(3 - всреднем)

;**************************************3-х уровневая**************************
;**********************************1-типная*************************** ******

4)N - Кол-во команд, ушедших до 3-го уровня. Т.е на 2-м уровне осталось С-N команд.
5) Пусть Z – кол-во символов на 3-м уровне.

Для буферного метода: V(X)=
(С- N)*[X + Y]*(A+04) + N*[Z + X + Y]*(A+04) + [Z+X+Y+1] (это буффер)
Для метода c деревьями: V(X)=
(1+4+4+4+(04+A))*[X +(С-N)*Y + N*Z] + (X+ (С-N)*Y + N*Z)*(3 - всреднем)


В аттаче таблица с данными.

З.Ы.:
Самому было интересно, вот и проверил. Вроде не ошибся. Т.О. при >2 – х уровневых командах, уже встречаются приравнивание размеров динамических структур. Статические – конечно же меньше у метода с деревьями. Но вот, всё в чём проблема – так это очень маленькая скорость метода с деревьями. Решил, когда допишу до конца метод с деревьями, заняться буферным.

Надеюсь на комментарии. --==PPS==--


1801042346__KeyStrokes.xls

Хм.. ну уже математика пощла :)
Я вот накидал рабочий примерчик - у меня данные немного по-другому хранятся, соответственно весят немного меньше (учитывая возросшее кол-во полезных данных).
+ Код 106 байт. (осталось только добавить заполнение буфера).
Работает довольно быстро - за работой наблюдать в отладчике.

        ; fasm
        format pe
        entry  check

                ;  '0123456789abcdef'
input_buffer    db 'xxxxxxxBeepMode2'

        align   4

size__6:        ;89abcdef
        dd      handle_BeepOn
        db      '..BeepOn'
        dd      0

size__7:        ;89abcdef
        dd      handle_BeepOff
        db      '.BeepOff'
        dd      0

size__8:        ;89abcdef
        dd      show_tip_BeepMode
        db      'BeepMode'
        dd      0

size__9:        ;456789abcdef
        dd      handle_BeepMode1
        db      '...BeepMode1'
        dd      handle_BeepMode2
        db      '...BeepMode2'
        dd      0

size_10:
size_12:
        dd      0

size_11:        ;456789abcdef
        dd      show_tip_BeepModeVol
        db      '.BeepModeVol'
        dd      0

size_13:        ;0123456789abcdef
        dd      handle_BeepModeVolUp
        db      '...BeepModeVolUp'
        dd      0

size_14:        ;0123456789abcdef
        dd      handle_BeepModeVolOff
        db      '..BeepModeVolOff'
        dd      0

size_15:
        dd      handle_BeepModeVolDown
        db      '.BeepModeVolDown'
        dd      0

map     = $ - 4*6
        dd      size__6, size__7
        dd      size__8, size__9
        dd      size_10, size_11
        dd      size_12, size_13
        dd      size_14, size_15


check:
        push    15
        pop     ebx

check_ebx_keys:
        mov     esi, [map+ebx*4]
        mov     ecx, ebx
        ; mask
        shl     ecx, 3
        xor     edx, edx
        dec     edx
        shr     edx, cl
        not     edx
        ; input buffer address
        mov     edi, 16+input_buffer
        sub     edi, ebx
        and     edi, -4
        ; switch
        mov     ecx, ebx
        neg     ecx
        and     ecx, -4
        lea     ecx, [ecx*2+8*4+@f]

check_sequence:
        cmp     dword[esi],0
        jz      check_ebx_next
        jmp     ecx

check_next_sequence:
        lea     esi, [esi+ebx+3+4]
        and     esi, -4
        jmp     check_sequence

check_ebx_next:
        dec     ebx
        cmp     ebx, 6
        jnc     check_ebx_keys
        ret

@@:     mov     eax, [edi+0xC]
        cmp     [esi+0xC+4], eax
        jnz     check_next_sequence

        mov     eax, [edi+0x8]
        cmp     [esi+0x8+4], eax
        jnz     check_next_sequence

        mov     eax, [edi+0x4]
        cmp     [esi+0x4+4], eax
        jnz     check_next_sequence

        mov     eax, [edi]
        and     eax, edx
        and     edx, [esi+4]
        cmp     edx, eax
        jnz     check_next_sequence

        jmp     dword[esi]


handle_BeepOn:
handle_BeepOff:
show_tip_BeepMode:
handle_BeepMode1:
handle_BeepMode2:
show_tip_BeepModeVol:
handle_BeepModeVolUp:
handle_BeepModeVolOff:
handle_BeepModeVolDown:                     

1342120725__0.EXE

Благодарю!!! Учту такой вариант реализации этого алгоритма. По размерам и скорости... мда.. - базара нэма.