1

Тема: Алгоритм Шинглів

(Власне не сам алгоритм, а деякі його аспекти)

Добрий вечір. Хотів дізнатися деякі деталі стосовно С++ і роботи з текстами в С++.
Мені потрібно розібрати алгоритм Шинглів, я знайшов деякі документації але на Python'i, PHP та сам "голий" алгоритм. Я не буду просити створити мені приклад повністю робочої реалізації, мене інтересують лише деякі моменти, наприклад:
- яким чином саме можна зробити приведення всіх букв до нижнього регістру (наскільки я зрозумів це "Всі великі букви стають малими" (A -> a));
- яким чином можна реалізувати вилучення лишніх символів (";" , "%" , ":" , "." , "," ,"?" і т.д.).

Для вилучення, я гадаю, потрібно скористатися попередньо заданою послідовністю цих символів і вже перевіряти сам текст на їх присутність, але реалізація не піддається моєму розумінню (та для мене це питання не є найважливішим).

Найважкішим для мене є, саме, "нижній регістр" (думаю реалізація так, як з вилученням, тут буде не доцільною та громіздкою).
З наведених прикладів я мало що можу зрозуміти (якщо не рахувати "голий" алгоритм), в Python'i та PHP абсолютно не розбираюсь, тому з наведених прикладів я не зрозумів майже нічого.

Знайти документацію теж не так просто, як я вважав.
Якщо в вас є якась документація, або приклади, будь-які, я був би дуже вдячний вам за допомогу.

Прикладів моєї діяльності, які я сам розбирав, представити не можу, тому що в мене є лише невелика частинка даного проекта, яку я лише недавно реалізував і з якою я намагаюся працювати (на Delphi, якщо потрібно можу продемонструвати), а саме:
- відкриття першого текстового файлу (запис в Memo);
- відкриття другого текстового файлу (також запис в Memo).

P.S. Сам весь проект має бути написаний на С++ з елементами ООП, але докищо я розбираю по шматочкам і в тих середовищах в яких я ще більш-меньш орієнтуюся. Якщо будуть якісь ідеї які піддаються реалізації лише на С++, прошу якось відмітити це (якщо це не буде занадто важко).

P.S.S. Розумію, що без прикладів своєї роботи, мало що можна отримати, але я все-ж-таки маю надію хоч на якусь допомогу з вашого боку.

"Most good programmers do programming not because they expect to get paid or get adulation by the public, but because it is fun to program."
- Linus Torvalds

2

Re: Алгоритм Шинглів

цикли, буфера і http://www.cplusplus.com/reference/cctype/tolower/ вам у руки

Бодай вас Бог любив, а мене – молодиці!
Подякували: Logans1

3 Востаннє редагувалося koala (19.11.2013 20:48:58)

Re: Алгоритм Шинглів

Найтупішний (і чи не найшвидший, якщо не враховувати оптимізації для конкретних процесорів) варіант - перебираємо рядок по символу и перекидаємо в новий рядок те, що треба (малий символ для великих, нічого для зайвих і той, що й був, для решти).
Як "зменшити" реєстр? Є кілька варіантів. Сучасні реалізації C++ можуть підтримувати tolower з <locale> для цієї мети; для старших доведеться писати вручну. Найшвидше - типу такого:

char lower(char ch)
{
  if(/*символ ch в списку великих*/)
  {
    ch+='а'-'А';
    /*ще якісь перетворення для "особливих" випадків, типу ґ*/
  }
  return ch;
}

Звісно, щоб розібратися, які саме символи - великі, і як їх призводити, треба дослідити відповідну таблицю символів. Якщо не хочете із цим копирсатися - робіть тупіше (знову ж таки, в різних таблицях):

char lower(char ch)
{
  char *caps="АБВГҐД....ЮЯ";
  char *p=strchr(capse,ch);
  if(!p)return ch;
  else return "абвгґд...юя"[p-caps];
}

Так, і char може означати wchar_t для юнікоду.

Подякували: Logans1

4 Востаннє редагувалося Logans (19.11.2013 20:30:35)

Re: Алгоритм Шинглів

В мене є одна ідея, але я таких прикладі не знаю, та і якась вона досить не в гарному стилі.
Наскільки я розумію кожен символ окремо має свій ASCII код, наприклад символ "А" має код 26, а символ "а" 55 і символ "Б" має код 27, а символ "б" 56, чи не можна до коду великого добавляти різницю кодів малого та великого. Різниця, як я розумію, в таблиці стала величина.

Хоча краще яб цого не писав (тому що, можу ще щось не те сказати).

"Most good programmers do programming not because they expect to get paid or get adulation by the public, but because it is fun to program."
- Linus Torvalds

5 Востаннє редагувалося koala (19.11.2013 20:48:48)

Re: Алгоритм Шинглів

Oleg написав:

В мене є одна ідея, але я таких прикладі не знаю, та і якась вона досить не в гарному стилі.
Наскільки я розумію кожен символ окремо має свій ASCII код, наприклад символ "А" має код 26, а символ "а" 55 і символ "Б" має код 27, а символ "б" 56, чи не можна до коду великого добавляти різницю кодів малого та великого. Різниця, як я розумію, в таблиці стала величина.

Хоча краще яб цого не писав (тому що, можу ще щось не те сказати).

Для більшості символів і більшості кодувань - так (на рядок  ch+='а'-'А'; увагу зверніть). Але є винятки, досить суттєві. І в кирилиці немає кодів ASCII, ASCII кодує тільки латиницю (7 біт).

Подякували: Logans1

6

Re: Алгоритм Шинглів

А поєднати ToLower та "тупіший" метод (для "і", та "ґ") можливо взагалі?

"Most good programmers do programming not because they expect to get paid or get adulation by the public, but because it is fun to program."
- Linus Torvalds

7 Востаннє редагувалося koala (21.11.2013 21:57:44)

Re: Алгоритм Шинглів

1. Немає метода ToLower (принаймні, стандартного), а є tolower і Windows Forms-ний String::ToLower, про який я тут не згадував.
2. tolower (як і String::ToLower) або працює з усією кирилицею, або не працює з нею взагалі (принаймні, мені так здається). Тому питання позбавлено сенсу. Може, уточните?

Подякували: Logans1

8

Re: Алгоритм Шинглів

koala написав:

1. Немає метода ToLower (принаймні, стандартного), а є tolower і Windows Forms-ний String::ToLower, про який я тут не згадував.
2. tolower (як і String::ToLower) або працює з усією кирилицею, або не працює з нею взагалі (принаймні, мені так здається). Тому питання позбавлено сенсу. Може, уточните?

1.
  а) Написав "ToLower" тому що, з Паскаля звик "окреме" слово писати з великої букви (перевчаюся);
  b) Саме для Windows Forms, в майбутньому, мені і потрібно буде його використовувати.
2. Уточнити на даний момент не можу, тому що, ще мало що розумію.

"Most good programmers do programming not because they expect to get paid or get adulation by the public, but because it is fun to program."
- Linus Torvalds

9 Востаннє редагувалося koala (22.11.2013 12:22:09)

Re: Алгоритм Шинглів

1.b) Давайте розберемося з поняттями. Програмування на C++ складається з:
- самого C++ (зокрема, того, що великі літери в ідентифікаторах відрізняються від маленьких);
- стандартної бібліотеки STL (зокрема, заголовку locale і функції tolower);
- купи різних прикладних бібліотек, часто прив'язаних до конкретного середовища розробки.
Серед таких бібліотек:
- VCL;
- MFC/WinAPI;
- Windows Forms (графічний інтерфейс .NET);
- Qt;
- wxWidgets;
і ще купа всякого різного. Деталі гугліть.
Ну так от, ваш код - це не .NET; це стандартні бібліотеки + адаптований до WinAPI шматок... кгм... DOSAPI, не знаю, як правильно це називалося(функція getch з conio.h). Може, вам все ж не Windows Forms, а щось інше графічне треба?
2. Тоді наводьте код, що у вас вийшло. Чи ви навіть нагуглити опис функції tolower не змогли?

10

Re: Алгоритм Шинглів

koala написав:

1.b) Давайте розберемося з поняттями. Програмування на C++ складається з:
- самого C++ (зокрема, того, що великі літери в ідентифікаторах відрізняються від маленьких);
- стандартної бібліотеки STL (зокрема, заголовку locale і функції tolower);
- купи різних прикладних бібліотек, часто прив'язаних до конкретного середовища розробки.
Серед таких бібліотек:
- VCL;
- MFC/WinAPI;
- Windows Forms (графічний інтерфейс .NET);
- Qt;
- wxWidgets;
і ще купа всякого різного. Деталі гугліть.
Ну так от, ваш код - це не .NET; це стандартні бібліотеки + адаптований до WinAPI шматок... кгм... DOSAPI, не знаю, як правильно це називалося(функція getch з conio.h). Може, вам все ж не Windows Forms, а щось інше графічне треба?
2. Тоді наводьте код, що у вас вийшло. Чи ви навіть нагуглити опис функції tolower не змогли?


1. На данный момент я користуюся лише консольним режимом С++, але в майбутньому, мій проект, з використанням алгоритму Шинглів, потрібно буде зробити в "Приложение Windows Forms", тільки це я і хотів сказати.

2. В мене є працююча, невелика, програмка, але вона не працює з симолами "Іі" та "Ґґ", я лише хотів спитати чи можна поєднати ф-ію tolower з певними виключенями, але сам зрозумів, що якщо символи "Іі" та "Ґґ" не розпізнаються, то і поєднання нічого не дасть, тому що символи просто будуть як "??".

Код програми

#include "stdafx.h"
#include <iostream>

using namespace std;

int main()
{
    int i=0;
    setlocale(0,"");
    char str[]="А Б В Г Д Е Ї І Є Ж З Ґ.\n";
    char c;
    while (str[i])
    {
      c=str[i]; 
      putchar (tolower(c));
      cout << c;
      i++;
    };

    system("pause");
    return 0;
}

Результат програми

аА  бБ  вВ  гГ  дД  еЕ  їЇ  ??  єЄ  жЖ  зЗ  ??

На питання по ф-ії tolower, та "Як "зменшити" реєстр?" я отримав відповідь, дякую.
Але з'явились інші запитання, як активувати вивід "Іі" та "Ґґ", гадаю це вже мені прийдеться самому дізнатися.
В будь-якому випадку, Дякую за допомогу.

"Most good programmers do programming not because they expect to get paid or get adulation by the public, but because it is fun to program."
- Linus Torvalds

11

Re: Алгоритм Шинглів

В консолі Windows кодування 866. Так, дрібном'якенькі - загальмовані кацапи, що ж поробиш.