Giải thuật và lập trình - C: IV. Từ điển (DICTIONARY)


Đăng ký nhận thông báo về những video mới nhất

IV. Từ điển (DICTIONARY)

Từ điển là một kiểu dữ liệu trừu tượng tập hợp đặc biệt, trong đó chúng ta chỉ quan tâm đến các phép toán InsertSet, DeleteSet, Member và MakeNullSet. Sở dĩ chúng ta nghiên cứu từ điển là do trong nhiều ứng dụng không sử dụng đến các phép toán hợp, giao, hiệu của hai tập hợp. Ngược lại ta cần một cấu trúc làm sao cho việc tìm kiếm, thêm và bớt phần tử có phần hiệu quả nhất gọi là từ điển. Chúng ta cũng chấp nhận MakeNullSet như là phép khởi tạo cấu trúc.

1. Cài đặt từ điển bằng mảng

Thực chất việc cài đặt từ điển bằng mảng hoàn toàn giống với việc cài đặt danh sách đặc không có thứ tự.

Khai báo

#define MaxLength ... // So phan tu toi da

typedef ... ElementType; // Kieu du lieu trong tu dien

typedef int Position;

typedef struct

{

    ElementType Data[MaxLength];

    Position Last;

} SET;

Khởi tạo cấu trúc rỗng

void MakeNullSET(SET *L)

{

    (*L).Last=0;

}

Hàm kiểm tra thành viên của tập hợp

int Member(ElementType X, SET L)

{

    Position P=1, Found=0;

    while ((P <= (L.Last)) && (Found == 0))

        if ((L.Data[P]) == X) Found = 1;

        else P++;

    return Found;

}

Thêm một phần tử vào tập hợp

Vì danh sách không có thứ tự nên ta có thể thêm phần tử mới vào cuối danh sách.

void InsertSET(ElementType X, SET *L)

{

    if (FullSET(*L)) printf("Tap hop day");

    else if (Member(X,*L)==0)

    {

        (*L).Last++; (*L).Data[(*L).Last]=X;

    }

    else

        printf ("\nPhan tu da ton tai trong tu dien");

}

Xóa một phần tử trong tập hợp

Để xoá một phần tử nào đó ta phải tiến hành tìm kiếm nó trong danh sách. Vì danh sách không có thứ tự nên ta có thay thế phần tử bị xoá bằng phần tử cuối cùng trong danh sách để khỏi phải dời các phần tử nằm sau phần tử bị xoá lên một vị trí.

void DeleteSET(ElementType X, SET *L)

{

    if (EmptySET(*L)) printf("Tap hop rong!");

    else

    {

        Position Q=1;

        while ((Q<=(*L).Last)&& ((*L).Data[Q]!=X)) Q++;

        if ( (*L).Data[Q]==X)

        {

            for (int i=Q;i<(*L).Last;i++)

                (*L).Data[i]=(*L).Data[i+1];

            (*L).Last--;

        }

    }

}

Cài đặt tự điển bằng mảng đòi hỏi tốn n phép so sánh để xác định xem một phần tử có thuộc từ điển n phần tử hay không thông qua hàm Member. Trên từ điển, việc tìm kiếm một phần tử được xác định bằng hàm Member sẽ thường xuyên được sử dụng. Do đó, nếu hàm Member thực hiện không hiệu quả sẽ làm giảm đi ý nghĩa của từ điển (vì nói đến từ điển là phải tìm kiếm nhanh chóng). Mặt khác hàm Member còn được gọi từ trong thủ tục InsertSet và nó cũng dẫn đến là thủ tục này cũng không hiệu quả. Kỹ thuật băm cho phép chúng ta khắc phục nhược điểm trên.

2. Cài đặt từ điển bằng bảng băm

2.1 Cài đặt từ điển bằng bảng băm mở:

Định nghĩa bảng băm mở :

Băm mở là một mảng một chiều có B phần tử có chỉ số từ 0 đến B-1. Mỗi phần tử là một con trỏ, trỏ tới một danh sách liên kết mà dữ liệu sẽ của từ điển sẽ được lưu trong các danh sách liên kết này. Mỗi danh sách được gọi là một Bucket (một danh sách có chứa các phần tử có cùng giá trị hàm băm).

Hàm băm:

Hàm băm là một ánh xạ từ tập dữ liệu A đến các số nguyên 0..B-1 (h : A → 0..B-1); Theo đó giả sử x ∈ A thì h(x) là một số nguyên 0≤h(x)≤B-1. Có nhiều cách để xây dựng hàm băm, cách đơn giản nhất là ‘nguyên hóa x‘ và sau đó lấy h(x) = x % B.

Ví dụ : Cho tập hợp A = {1,5,7,2,4,15}

Bảng băm là mảng gồm 5 phần tử và hàm băm h(x) = x % 5; Ta có bảng băm lưu trữ A như sau :

Bảng băm

Hình IV.1: Bảng băm mở

Hàm băm có thể được thiết kế như sau

//Ham bam H(X)=X Mod B int H(ElementType X)

{

    return X%B;

}

Sử dụng bảng băm mở để cài đặt từ điển

Dưới đây là các thủ tục cài đặt từ điển bằng bảng băm mở với giả thiết rằng các phần tử trong từ điển có kiểu ElementType và hàm băm là H.

Khai báo

#define B ...

typedef ... ElementType;

typedef struct Node

{

    ElementType Data;

    Node* Next;

};

typedef Node* Position;

typedef Position Dictionary[B];

Khởi tạo bảng băm mở rỗng

Lúc này tất cả các bucket là rỗng nên ta gán tất cả các con trỏ trỏ đến đầu các danh sách trong mỗi bucket là NULL.

void MakeNullSet(Dictionary *D)

{

    for(int i=0;i<B;i++) (*D)[i]=NULL;

}

Kiểm tra một thành viên trong từ điển được cài bằng bảng băm mở

Để kiểm tra xem một khoá x nào đó có trong từ điển hay không, ta tính địa chỉ của nó trong bảng băm. Theo cấu trúc của bảng băm thì khoá x sẽ nằm trong bucket được trỏ bởi D[h(x)], với h(x) là hàm băm. Như vậy để tìm khoá x trước hết ta phải tính h(x) sau đó duyệt danh sách của bucket được trỏ bởi D[h(x)]. Giải thuật như sau:

int Member(ElementType X, Dictionary D)

{

    Position P;

    int Found=0;

    //Tim o muc H(X) P=D[H(X)];

    //Duyet tren ds thu H(X)

    while((P!=NULL) && (!Found))

        if (P->Data==X) Found=1;

        else P=P->Next;

    return Found;

}

Thêm một phần tử vào từ điển được cài bằng bảng băm mở

Để thêm một phần tử có khoá x vào từ điển ta phải tính bucket chứa nó, tức là phải tính h(x). Phần tử có khoá x sẽ được thêm vào bucket được trỏ bởi D[h(x)]. Vì ta không quan tâm đến thứ tự các phần tử trong mỗi bucket nên ta có thể thêm phần tử mới ngay đầu bucket này. Giải thuật như sau:

void InsertSet(ElementType X, Dictionary *D)

{

    int Bucket;

    Position P;

    if (!Member(X,*D))

    {

        Bucket=H(X);

        P=(*D)[Bucket];

        //Cap phat o nho moi cho

        *D[Bucket] (*D)[Bucket] = (Node*)malloc(sizeof(Node));

        (*D)[Bucket]->Data=X;

        (*D)[Bucket]->Next=P;

    }

}

Xoá một phần tử trong từ điển được cài bằng bảng băm mở

Xoá một phần tử có khoá x trong từ điển bao gồm việc tìm ô chứa khoá và xoá ô này. Phần tử x, nếu có trong từ điển, sẽ nằm ở bucket D[h(x)]. Có hai trường hợp cần phân biệt. Nếu x nằm ngay đầu bucket, sau khi xoá x thì phần tử kế tiếp sau x trong bucket sẽ trở thành đầu bucket. Nếu x không nằm ở đầu bucket thì ta duyệt bucket này để tìm và xoá x. Trong trường hợp này ta phải định vị con trỏ duyệt tại "ô trước" ô chứa x để cập nhật lại con trỏ Next của ô này. Giải thuật như sau:

void DeleteSet(ElementType X, Dictionary *D)

{

    int Bucket, Done;

    Position P,Q;

    Bucket=H(X);

    // Neu danh sach ton tai

    if ((*D)[Bucket]!=NULL)

    {

        // X o dau danh sach

        if ((*D)[Bucket]->Data==X)

        {

            Q=(*D)[Bucket];

            (*D)[Bucket]=(*D)[Bucket]->Next;

            free(Q);

        }

        else // Tim X

        {

            Done=0;

            P=(*D)[Bucket];

            while ((P->Next!=NULL) && (!Done))

                if (P->Next->Data==X) Done=1;

                else P=P->Next;

            // Neu tim thay

            if (Done)

            {

                //Xoa P->Next

                Q=P->Next;

                P->Next=Q->Next;

                free(Q);

            }

        }

    }

}

2.2. Cài đặt từ điển bằng bảng băm đóng

Định nghĩa bảng băm đóng :

Bảng băm đóng lưu giữ các phần tử của từ điển ngay trong mảng chứ không dùng mảng làm các chỉ điểm đầu của các danh sách liên kết. Bucket thứ i chứa phần tử có giá trị băm là i, nhưng vì có thể có nhiều phần tử có cùng giá trị băm nên ta sẽ gặp trường hợp sau: ta muốn đưa vào bucket i một phần tử x nhưng bucket này đã bị chiếm bởi một phần tử y nào đó (đụng độ). Như vậy khi thiết kế một bảng băm đóng ta phải có cách để giải quyết sự đụng độ này.

Giải quyết đụng độ :

Cách giải quyết đụng độ đó gọi là chiến lược băm lại (rehash strategy). Chiến lược băm lại là chọn tuần tự các vị trí h1,..., hk theo một cách nào đó cho tới khi gặp một vị trí trống để đặt x vào. Dãy h1,..., hk gọi là dãy các phép thử. Một chiến lược đơn giản là băm lại tuyến tính, trong đó dãy các phép thử có dạng :

Giải quyết đụng độ

Ví dụ B=8 và các phần tử của từ điển là a,b,c,d có giá trị băm lần lượt là: h(a)=3, h(b)=0, h(c)=4, h(d)=3. Ta muốn đưa các phần tử này lần lượt vào bảng băm.

Khởi đầu bảng băm là rỗng, có thể coi mỗi bucket chứa một giá trị đặc biệt Empty, Empty không bằng với bất kỳ một phần tử nào mà ta có thể xét trong tập hợp các phần tử muốn đưa vào bảng băm.

Ta đặt a vào bucket 3, b vào bucket 0, c vào bucket 4. Xét phần tử d, d có h(d)=3 nhưng bucket 3 đã bị a chiếm ta tìm vị trí h1(x)= (h (x)+1) mod B = 4, vị trí này cũng đã bị c chiếm, tiếp tục tìm sang vị trí h2 (x)= (h(x)+2) mod B= 5 đây là một bucket rỗng ta đặt d vào (xem hình IV.2)

Bảng băm

Hình IV.2: Giải quyết đụng độ trong bảng băm đóng bằng chiến lược băm lại tuyến tính

Trong bảng băm đóng, phép kiểm tra một thành viên(thủ tục MEMBER (x,A)) phải xét dãy các bucket h(x),h1(x),h2(x),... cho đến khi tìm thấy x hoặc tìm thấy một vị trí trống. Bởi vì nếu hk(x) là vị trí trống được gặp đầu tiên thì x không thể được tìm gặp ở một vị trí nào xa hơn nữa. Tuy nhiên, nói chung điều đó chỉ đúng với trường hợp ta không hề xoá đi một phần tử nào trong bảng băm. Nếu chúng ta chấp nhận phép xoá thì chúng ta qui ước rằng phần tử bị xóa sẽ được thay bởi một giá trị đặc biệt, gọi là Deleted, giá trị Deleted không bằng với bất kỳ một phần tử nào trong tập hợp đang xét vào nó cũng phải khác giá trị Empty. Empty cũng là một giá trị đặc biệt cho ta biết ô trống.

Ví dụ

  - Tìm phần tử e trong bảng băm trên, giả sử h(e)=4. Chúng ta tìm kiếm e tại các vị trí 4,5,6. Bucket 6 là chứa Empty, vậy không có e trong bảng băm.

  - Tìm d, vì h(d)=3 ta khởi đầu tại vị trí này và duyệt qua các bucket 4,5. Phần tử d được tìm thấy tại bucket 5.

Sử dụng bảng băm đóng để cài đặt từ điển

Dưới đây là khai báo và thủ tục cần thiết để cài đặt từ điển bằng bảng băm đóng. Để dễ dàng minh hoạ các giá trị Deleted và Empty, giả sử rằng ta cần cài đặt từ điển gồm các chuỗi 10 kí tự. Ta có thể qui ước:

Empty là chuỗi 10 dấu + và Deleted là chuỗi 10 dấu *.

Khai báo

#define B 100

#define Deleted -1000//Gia dinh gia tri cho o da bi xoa

#define Empty 1000 //Gia dinh gia tri cho o chua su dung

typedef int ElementType;

typedef int Dictionary [B];

Tạo hàm băm

int H (ElementType X)]

{

    return X%B;

}

Tạo tự điển rỗng

// Tao tu dien rong

void MakeNullDic(Dictionary D){

    for (int i=0;i<B; i++)

        D[i]=Empty;

}

Kiểm tra sự tồn tại của phần tử trong tự điển

Hàm trả về giá tri 0 nếu phần tử X không tồn tại trong tự điển; Ngược lại, hàm trả về giá trị 1;

int Member(ElementType X, Dictionary D)

{

    Position init=H(X), i=0;

    while ((i<B) && (D[i]!=Empty) && (D[i]!=X)) i++;

    return (D[i]==X);

}

Thêm phần tử vào tự điển

void InsertDic(ElementType X, Dictionary D)

{

    int i=0,init;

    if (FullDic(D))

        printf("Bang bam day");

    else if (Member(X,D)==0)

    {

        init=H(X);

        while((i<B)&&(D[(i+init)%B]!=Empty)&&(D[(i+init)%B]!=Deleted)) i++;

        D[(i+init)%B]=X;

        printf("\n Vi tri de xen phan tu %d la %d\n",X,(i+init)%B);

    }

    else

        printf ("\nPhan tu da ton tai trong bang bam");

}

Xóa từ ra khỏi tự điển

void DeleteDic(ElementType X, Dictionary D)

{

    if (EmptyDic(D)) printf("\nBang bam rong!");

    else

    {

        int i=0,init =H(X);

        while((i<B)&&(D[(i+init)%B]!=X)&&(D[(i+init)%B]!=Deleted)) i++;

        if ( D[(i+init)%B]==X) D[(i+init)%B]=Deleted;

    }

}

3. Các phương pháp xác định hàm băm

Phương pháp chia

"Lấy phần dư của giá trị khoá khi chia cho số bucket" . Tức là hàm băm có dạng:

  H(x)= x mod B

Phương pháp này rõ ràng là rất đơn giản nhưng nó có thể không cho kết quả ngẫu nhiên lắm. Chẳng hạn B=1000 thì H(x) chỉ phụ thuộc vào ba số cuối cùng của khoá mà không phụ thuộc vào các số đứng trước. Kết quả có thể ngẫu nhiên hơn nếu B là một số nguyên tố.

Phương pháp nhân

"Lấy khoá nhân với chính nó rồi chọn một số chữ số ở giữa làm kết quả của hàm băm".

Ví dụ:

Ví dụ

 

Vì các chữ số ở giữa phụ thuộc vào tất cả các chữ số có mặt trong khoá do vậy các khoá có khác nhau đôi chút thì hàm băm cho kết quả khác nhau.

Phương pháp tách

Đối với các khoá dài và kích thước thay đổi người ta thường dùng phương pháp phân đoạn, tức là phân khoá ra thành nhiều đoạn có kích thước bằng nhau từ một đầu (trừ đoạn tại đầu cuối), nói chung mỗi đoạn có độ dài bằng độ dài của kết quả hàm băm. Phân đoạn có thể là tách hoặc gấp:

a. Tách:

Tách khóa ra từng đoạn rồi xếp các đoạn thành hàng được canh thẳng một đầu  rồi có thể cộng chúng lại rồi áp dụng phương pháp chia để có kết quả băm.

    Ví dụ: khoá 17046329 tách thành

        329

        046

        017

    cộng lại ta được 392. 392 mod 1000 = 392 là kết quả băm khoá đã cho.

b. Gấp:

Gấp khoá lại theo một cách nào đó, có thể tương tự như gấp giấy, các chữ số cùng nằm tại một vị trí sau khi gấp được xếp lại thẳng hàng với nhau rồi có thể cộng lại rồi áp dụng phương pháp chia (mod) để cho kết quả băm.

Ví dụ: khoá 17046329 gấp hai biên vào ta có

  932

  046

  710

Cộng lại ta có 1679, lấy 1679 mod 1000 = 679 là kết quả băm khoá đã cho.


Nếu bạn có điều thắc mắc, bạn hãy comment cho V1Study để được giải đáp.
Bài viết này được chia sẻ bởi LongDT. Nếu bạn muốn chia sẻ bài viết, bạn hãy Đăng ký làm thành viên!
« Prev
Next »
Copied !!!