Как определить частоту слов в введенной пользователем строке на языке ассемблера X86?

Я полный новичок в программировании на ассемблере. Мне нужна помощь в написании программы на ассемблере, чтобы получить строку от пользователя, подсчитать и отобразить количество раз, когда каждое слово встречается в введенной пользователем строке.

Например, если пользователь вводит:

Hello Hello what is new Hello what is not new

Вывод должен быть:

Hello   3
what    2
is      2
not     1
new     2

У меня есть следующий код ниже, который даст мне частоту символов в строке. Однако я не знаю, как редактировать, чтобы отслеживать слова, а не только символы, а затем отображать эти слова с соответствующей частотой.

INCLUDE Irvine32.inc

Get_frequencies PROTO,
    pString:PTR BYTE,   ; points to string
    pTable:PTR DWORD    ; points to frequency table

.data
freqTable DWORD 256 DUP(0)
;aString BYTE 1,2,"This is extremely difficult for the experienced",0

aString BYTE 80 DUP(0),0

str1 BYTE "*** Constructing a Frequency Table *** (DEMO)",
    0dh,0ah,0dh,0ah,
    "Enter between 1 and 80 characters: ",0

.code
main PROC

    call Clrscr
    mov  edx,OFFSET str1
    call WriteString

    mov  ecx,SIZEOF aString - 1
    mov  edx,OFFSET aString
    call ReadString

    INVOKE Get_frequencies, ADDR aString, ADDR freqTable
    call DisplayTable

   exit
   main ENDP

;-------------------------------------------------------------

  Get_frequencies PROC,
    pString:PTR BYTE,   ; points to string
    pTable:PTR DWORD    ; points to frequencey table

;
; Constructs a character frequency table. Each array position
; is indexed by its corresponding ASCII code.
;
; Returns: Each entry in the table contains a count of how
; many times that character occurred in the string.
;-------------------------------------------------------------

mov esi,pString
mov edi,pTable
cld     ; clear Direction flag (forward)

L1: mov eax,0       ; clear upper bits of EAX
   lodsb        ; AL = [ESI], inc ESI
   cmp al,0     ; end of string?
   je  Exit_proc        ; yes: exit
   shl eax,2        ; multiply by 4
   inc DWORD PTR [edi + eax]    ; inc table[AL]
   jmp L1       ; repeat loop

 Exit_proc:
    ret
 Get_frequencies ENDP

  ;-------------------------------------------------------------

 DisplayTable PROC

  ;
  ; Display the non-empty entries of the frequency table.
  ; This procedure was not required, but it makes it easier
  ; to demonstrate that Get_frequencies works.
  ;-------------------------------------------------------------

  .data
  colonStr BYTE ": ",0
  .code
  call Crlf
  mov ecx,LENGTHOF freqTable    ; entries to show
  mov esi,OFFSET freqTable
  mov ebx,0 ; index counter

 L1:    mov eax,[esi]   ; get frequency count
        cmp eax,0   ; count = 0?
        jna L2  ; if so, skip to next entry

         mov eax,ebx    ; display the index
         call WriteChar
         mov edx,OFFSET colonStr    ; display ": "
         call WriteString
         mov eax,[esi]  ; show frequency count
         call WriteDec
         call Crlf

  L2:   add esi,TYPE freqTable  ; point to next table entry
        inc ebx ; increment index
        loop L1

        call Crlf
        ret
      DisplayTable ENDP

      END main

Это то, что у меня есть до сих пор в моей попытке реализовать поиск грубой силы, предложенный в ответе Питера:

 .data
 str2 BYTE "one two three",0

 .code
  main proc
   mov  edi,OFFSET str2
    Mov esi,edi
    Mov Ecx, 0  ;reset ecx to 0
    Not Ecx     ;set Ecx to -1 or highest possible integer
    Mov Al, ' ' ;Initialize a1 to delimiter of (space) ' '
    Cld         ;Clear Direction Pointer
    Repne Scasb ;scan edi one byte at a time until delimiter found
    Not Ecx
    Lea Eax, [ecx-1] ;Set Eax to index of found delimiter
    Xchg Esi, Edi  ;Take Edi which is now equal to string after found       delimiter and put in esi

    mov edx, esi
    call WriteString    

 main endp
 end main

Это печатает «два три», но я хочу, чтобы он печатал «один».


x86 text-processing assembly masm irvine32
person coderintraining    schedule 18.05.2016    source источник
comment
Не забывайте смотреть на то, что вы публикуете, и редактируйте его, если оно выглядит не так. Мне пришлось повторно отредактировать ваш вопрос, чтобы отделить новый код от предыдущего дампа кода.   -  person Peter Cordes    schedule 21.05.2016
comment
Вы передаете конец найденного слова в WriteString. Вот почему он печатает остальную часть строки. Это говорит о том, что ваш код работал и остановился после первого слова. Какие аргументы принимает WriteString? Я никогда не использовал Irvine32. Если для этого требуется указатель и длина, вы сможете его использовать. В противном случае, если он просто печатает до 0-терминатора, вы не можете использовать его таким образом. (Вы можете заменить ' ' разделителем '\0', но это имеет значение только для отладочной печати.)   -  person Peter Cordes    schedule 21.05.2016
comment
Почему бы тебе просто mov ecx, -1 не вести себя как нормальный человек? Вы бы использовали только not ecx или dec ecx для экономии байтов при генерации -1, выполнив xor ecx,ecx / dec ecx (всего 3 байта в 32-битном коде, 4 байта в 64-битном коде) вместо mov ecx, -1 (5 байт). Кстати, я проверил, и WriteString просто печатает строку с завершающим нулем, переданную в edx. Я не знал, почему ты что-то вычисляешь в eax. Кстати, полезно сохранить длину слова для будущих циклов или rep cmpsb. (например, mov eax, ecx / neg eax, если только у меня нет ошибки "один на один".) Интересен не индекс разделителя.   -  person Peter Cordes    schedule 21.05.2016

Ответы (1)


arrow_upward
3
arrow_downward

В asm нет ничего особенного, что заставило бы вас выбрать другой алгоритм, чем если бы вы делали это на C или на любом другом языке, который вы уже знаете.

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

Имеется менее 128 печатных символов ASCII, поэтому таблица подсчета небольшая и простая.

Разница между символами и словами заключается в том, что количество возможных слов бесконечно (за исключением ограничений на размер памяти), поэтому вы не можете просто использовать слова непосредственно в качестве указателя в таблице подсчета. Даже использование 4-символьных слов в качестве 4-байтового индекса в таблице счетчиков приведет к тому, что размер таблицы счетчиков будет равен 2^32 записи.

Самый прямой способ адаптировать алгоритм таблицы подсчета от символов к словам — это использовать какой-то словарная структура данных, например хеш-таблица, дерево или даже основное дерево/дерево. Каждая запись сопоставляет слово со своим счетчиком.

Простейший возможный словарь word:count будет представлять собой несортированный массив
struct {char *word; int count;} histogram[];, в котором выполняется линейный поиск. Это неэффективно, но было бы легко реализовать на ассемблере. Сравнение слов можно ускорить, сохраняя строки явной длины, такие как int wordlen; char *wordstart, чтобы вы могли просто указать на свою строку без необходимости хранить 0 терминаторов. Затем вы можете проверить, имеют ли слова одинаковую длину, прежде чем смотреть на их байты, и memcmp может быть более эффективным, чем strcmp.

Это отстой, потому что это линейный поиск в этом массиве счетчиков для каждого входного слова, но это все же, вероятно, лучше, чем приведенный ниже метод грубой силы, который сканирует (и копирует) всю оставшуюся часть строки для каждого входного слова. Сохранение этого массива отсортированным (стиль сортировки вставками) может быть или не быть лучше, разрешая доступ O (log (n)) с двоичным поиском, когда слово найдено. Вероятно, есть умные компромиссы, такие как массивы с пробелами (со способом обозначения неиспользуемых слотов), которые могут позволить вставке в определенное место копировать только ограниченное количество. Или, конечно, классическая структура данных словаря, такая как хеш-таблица или дерево.

Другой вариант — отсортировать список слов, а затем прокрутить отсортированный список, подсчитывая дубликаты. Или накапливайте количество дубликатов во время сортировки, что представляет собой интересную проблему. когда ваш список входных слов слишком велик, чтобы поместиться в памяти сразу.

ваш текущий цикл char может быть лучше:

Вот что я мог бы сделать:

;; tighter version of your char-count loop
   xor   eax, eax                    ; clear upper bits of EAX
L1:
   lodsb                          ; AL = [ESI], inc ESI
   inc   DWORD PTR [edi + eax*4]  ; inc table[AL]
   test  al,al                    ; Set flags based on AL
   jz    L1                       ; loop if it's not the end of the string
   ;; fall through when done
   ;;dec   DWORD PTR [edi]          ; undo the count of the zero if you care

Или, что более вероятно, movzx eax, byte [esi]/inc esi, которые более эффективны, чем lodsb, и позволяют избежать затрат на слияние со старым EAX.

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

Поскольку мы сдвигаем влево как часть режима адресации нам не нужно обнулять eax внутри цикла. Используя xor-обнуление также позволяет избежать частичного замедления работы регистра при чтении eax после записи только al, если вы заботитесь о производительности.

Алгоритм грубой силы, который может быть проще реализовать на ассемблере

Это будет ужасно работать для длинных строк, но может быть довольно хорошим для очень коротких строк. Основным преимуществом является простота реализации, но по производительности он может конкурировать с деревом или хэшем для очень коротких строк, например 128 байт.

  • Найдите конец первого слова
  • Найдите в остатке строки вхождения этого слова. (Не забывайте сопоставлять только полные слова, а не strstr(3))
  • При каждом совпадении копируйте оставшуюся часть строки влево, удаляя слово из строки. (Удалите также первое слово.)
  • Повторяйте, пока строка не станет пустой

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

Это тратит много времени на копирование символов, но нам нужно избегать дубликатов (выполняя еще один подсчет для последних n-1 вхождений слова, когда мы подойдем к этому позже). Повторная проверка путем поиска в другой структуре данных уже подсчитанных слов позволит вам избежать копирования, но если вы собираетесь это сделать, вы можете просто выполнить один проход по строке и гистограмме в этот словарь найденных слов, см. выше.

но это само по себе стоит дополнительных циклов и кода, и все будущие поиски будут искать эти уже подсчитанные слова. Если вы собираетесь использовать массив уже найденных слов, вы также можете

Вы можете выполнить копирование с помощью rep movsb, который, я думаю, все еще работает с перекрывающимися dst и src. (Но не быстро, если они тесно перекрываются).

Другой вариант - иметь второй буфер одинакового размера, поэтому вы делаете только одну копию всей строки, удаляя все вхождения текущего слова, которое вы считаете:

Начиная со 2-го слова в строке A:

  • скопировать символы в строку B.
  • when you reach the end of a word, check if it's a match for the current word you're looking for.
    • if yes: count++ and dst-=length_of_current_countword. When you detect the word you're looking for, you rewind your destination pointer (edi) to the beginning, so future copying will overwrite it. I.e. you can un-copy it basically for free at this point.
  • повторяйте, пока не дойдете до конца строки A
  • напечатать текущее слово и количество.
  • Если строка B не является пустой, она становится новой строкой A и т. д. Возможно, храните указатели на A и B в регистрах или памяти, где вы можете поменять их местами, вместо того, чтобы напрямую использовать адрес статического хранилища. Или просто сделайте это глупым способом и скопируйте B в A без изменений.
person Peter Cordes    schedule 18.05.2016
comment
Привет, Петр, спасибо за ответ. Что касается вашего алгоритма грубой силы, как мне выполнить первые несколько шагов, которые вы описали? Должен ли я использовать разделитель и разбивать строку при первом появлении пробела? Затем, когда у меня есть слово, я должен сохранить его в массиве или регистре. Тогда как мне сравнить с остальной частью строки - person coderintraining; 18.05.2016
comment
@coderintraining: я представлял себе проверку символов, не являющихся словами, чтобы найти конец слова. Самым простым было бы найти первый " ". Вы не можете хранить слово в регистре, потому что он потенциально бесконечен. Вместо этого вы отслеживаете его начальную позицию с помощью указателя. (например, перед циклом копирования mov ecx, esi. Когда вы найдете конец слова, ecx указывает на начало, а esi-ecx — длину.). Вам не нужны никакие дополнительные массивы для копирования слов, но вам может понадобиться дополнительное пространство для переполнения указателей/длин, если у вас закончатся регистры. - person Peter Cordes; 19.05.2016
comment
Вы ищете остальную часть строки, используя тот же алгоритм, чтобы найти слова. Затем, если они имеют ту же длину, что и слово, которое вы ищете, memcmp с циклом или rep cmpsb. Это по-прежнему очень сложный алгоритм для реализации на ассемблере без каких-либо библиотечных функций. Вам разрешено вызывать строковые функции libc, такие как strtok? Это определенно слишком сложно для меня, чтобы представить все это в моей голове в том, какой регистр содержит какой уровень детализации, но каждый шаг сам по себе является чем-то довольно простым в ассемблере. - person Peter Cordes; 19.05.2016
comment
Я не могу вставить первое слово в регистр. скажем, моя строка - один два три, я использую следующий код, и он дает мне только два три - person coderintraining; 21.05.2016
comment
mov edi,OFFSET str2 Mov esi,edi Mov Ecx, 0 ;сбросить ecx на 0 Not Ecx ;установить Ecx на -1 или максимально возможное целое число Mov Al, ' ' ;Инициализировать a1 разделителем (пробел) ' ' Cld ;Очистить направление Pointer Repne Scasb ;сканировать edi по одному байту за раз, пока не будет найден разделитель Not Ecx Lea Eax, [ecx-1] ;установить Eax в индекс найденного разделителя Xchg Esi, Edi ;взять Edi, который теперь равен строке после найденного разделителя, и поместить в esi mov edx вызов esi WriteString - person coderintraining; 21.05.2016
comment
@coderintraining: вы же знаете, что неформатированный код в комментариях нечитабелен для всех, верно? Отредактируйте это в своем вопросе. В любом случае, вы не загружаете в регистры слова, а только указатели на них. Сохраните указатель на начало буфера перед поиском конца первого слова. - person Peter Cordes; 21.05.2016
comment
Извините, я не понял, что он не форматировал. Я только что отредактировал вопрос. Мой код внизу. Если сохранить точку, где начинается строка, и иметь точку, где заканчивается первое слово. Я пытался вычесть два, а затем поместить их в edx для отображения, но это тоже не работает. - person coderintraining; 21.05.2016