1

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

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

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

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

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

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

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

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

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

2

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

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

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

3 Востаннє редагувалося koala (19.11.2013 19: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 19:30:35)

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

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

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

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

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

Oleg написав:

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

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

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

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

6

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

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

7 Востаннє редагувалося koala (21.11.2013 20: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. Уточнити на даний момент не можу, тому що, ще мало що розумію.

9 Востаннє редагувалося koala (22.11.2013 11: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, та "Як "зменшити" реєстр?" я отримав відповідь, дякую.
Але з'явились інші запитання, як активувати вивід "Іі" та "Ґґ", гадаю це вже мені прийдеться самому дізнатися.
В будь-якому випадку, Дякую за допомогу.

11

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

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