Trung tâm cá nhân
sách gpt4 ăn đã đi

Thuật toán chuỗi Markov (thuật toán markov) awk, mã triển khai ngôn ngữ C++, C

In lại Tác giả: qq735679552 Thời gian cập nhật: 28-09-2022 22:32:09 50 4
mua khóa gpt4 giày nike

CFSDN nhấn mạnh vào giá trị tạo ra nguồn mở và chúng tôi cam kết xây dựng nền tảng chia sẻ tài nguyên để mọi nhân viên CNTT có thể tìm thấy thế giới tuyệt vời của bạn tại đây.

Bài viết trên blog CFSDN này có mã triển khai ngôn ngữ awk, C++ và C của thuật toán chuỗi Markov (thuật toán markov) được tác giả sưu tầm và biên soạn. Nếu bạn quan tâm đến bài viết này thì nhớ like nhé.

1. Mô tả vấn đề.

Thuật toán chuỗi Markov được sử dụng để tạo ra một đoạn tiếng Anh ngẫu nhiên và ý tưởng của nó rất đơn giản. Đầu tiên đọc dữ liệu, sau đó chia dữ liệu đã đọc thành hai phần: tiền tố và hậu tố, đồng thời lấy ngẫu nhiên hậu tố thông qua tiền tố, từ đó tạo ra một đoạn tiếng Anh ngẫu nhiên có thể đọc được.

Để thuận tiện cho việc giải thích, giả sử chúng ta có đoạn văn sau: .

Sao chép mã Mã này như sau:
   Hiển thị sơ đồ luồng công việc và che giấu các bảng của bạn và tôi sẽ thấy bối rối. Hiển thị các bảng của bạn và sơ đồ luồng công việc của bạn sẽ rõ ràng.

Giả sử độ dài của tiền tố là 2, sau khi xử lý dữ liệu đầu vào, chúng tôi nhận được dữ liệu sau, sau đó chọn ngẫu nhiên một từ từ danh sách hậu tố của tiền tố, sau đó thay đổi tiền tố và lặp lại thao tác trên. process. Bằng cách này, câu chúng tôi tạo ra sẽ có thể đọc được.

  。

Dưới đây là dữ liệu được xử lý:

Sao chép mã Mã này như sau:

hậu tố tiền tố
hiển thị các bảng biểu đồ luồng của bạn
sơ đồ luồng công việc của bạn và ý chí
sơ đồ và che giấu
sơ đồ sẽ là
bảng của bạn và và
sẽ trở nên bí ẩn. Rõ ràng.
bị làm cho bối rối. hiển thị
rõ ràng. (kết thúc)

Thuật toán chuỗi Markov xử lý văn bản này trước tiên sẽ dẫn đến hiển thị lưu đồ của bạn, sau đó chọn ngẫu nhiên hai từ lưu đồ hoặc bảng. Giả sử lưu đồ được chọn, tiền tố mới là lưu đồ của bạn. Tương tự, khi bảng được chọn, lưu đồ mới. tiền tố Đây là bảng của bạn Với tiền tố mới trong sơ đồ của bạn, hãy chọn lại hậu tố của nó, lần này chọn ngẫu nhiên giữa và sẽ. Lặp lại quy trình trên để tạo ra văn bản có thể đọc được. Mô tả cụ thể như sau:

Sao chép mã Mã này như sau:

  。

Đặt w1 và w2 thành hai từ đầu tiên của văn bản và xuất ra w1 và w2.

Vòng lặp: Chọn ngẫu nhiên w3, là một trong các hậu tố của w1 và w2 trong văn bản. Thay thế w1 và w2 bằng w2 và w3 tương ứng.

  。

chương trình 2.awk.

Thuật toán chuỗi Markov không khó, sau này chúng ta sẽ thấy rằng việc giải quyết vấn đề này bằng ngôn ngữ C sẽ khá rắc rối nhưng chỉ mất 5 phút để giải quyết bằng awk. Đây chỉ đơn giản là một câu hỏi thể hiện những ưu điểm của awk.

Có một mảng kết hợp trong awk, có thể được sử dụng để thể hiện mối quan hệ giữa tiền tố và hậu tố. Quy trình như sau:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# markov.awk: thuật toán chuỗi markov cho tiền tố 2 từ
BẮT ĐẦU { MAXGEN = 10000; KHÔNG PHẢI TỪ = "\N" ; w1 = w2 = KHÔNG PHẢI TỪ }
 
{  vì (i = 1; i <= NF; i++) {   # đọc tất cả các từ
     statetab[w1,w2,++nsuffix[w1,w2]] = $i
     w1 = w2
     w2 = $i
   }
}
 
KẾT THÚC {
   statetab[w1,w2,++nsuffix[w1,w2]] = KHÔNG TỪ # thêm đuôi
   w1 = w2 = KHÔNG PHẢI TỪ
   vì (i = 0; i < MAXGEN; i++) { # phát ra
     r = int(rand()*nsuffix[w1,w2]) + 1 # nsuffix >= 1
     p = statetab[w1,w2,r]
     nếu như (p == KHÔNG PHẢI TỪ)
       ra
     in p
     w1 = w2     # chuỗi tiến bộ
     w2 = p
   }
}

3. Chương trình C++.

Khó khăn chính của vấn đề này là lấy ngẫu nhiên hậu tố thông qua tiền tố. Trong C++, chúng ta có thể sử dụng bản đồ để nhận ra mối quan hệ tương ứng giữa tiền tố và hậu tố, nhằm đạt được hiệu quả phát triển cao hơn.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/* Bản quyền (C) 1999 Lucent Technologies */
/* Trích từ 'Thực hành lập trình' */
/* của Brian W. Kernighan và Rob Pike */
 
#include
#include
#include
#include
#include
#include
 
sử dụng không gian tên tiêu chuẩn;
 
hằng số số nguyên NPREF = 2;
hằng số char KHÔNG TỪ[] = "\N" ;  // không thể xuất hiện như dòng thực: chúng tôi xóa các dòng mới
hằng số số nguyên TỐI ĐA = 10000; // số từ tối đa được tạo ra
 
định nghĩa kiểu deque Tiền tố;
 
map > statetab; // tiền tố -> hậu tố
 
vô hiệu    xây dựng(Tiền tố&, istream&);
vô hiệu    phát ra( số nguyên từ);
vô hiệu    thêm(Tiền tố&, hằng số sợi dây&);
 
// markov main: tạo văn bản ngẫu nhiên markov-chain
số nguyên chủ yếu( vô hiệu )
{
   số nguyên nwords = TỐI ĐA;
   Tiền tố tiền tố; // tiền tố đầu vào hiện tại
 
   srand ( thời gian (VÔ GIÁ TRỊ));
   vì ( số nguyên i = 0; i < NPREF; i++)
     thêm(tiền tố, KHÔNG PHẢI TỪ);
   xây dựng(tiền tố, cin);
   thêm(tiền tố, KHÔNG PHẢI TỪ);
   tạo ra(nwords);
   trở lại 0;
}
 
// xây dựng: đọc các từ đầu vào, xây dựng bảng trạng thái
vô hiệu build(Tiền tố& tiền tố, istream& in)
{
   chuỗi đệm;
 
   trong khi (trong >> buf)
     thêm(tiền tố, buf);
}
 
// thêm: thêm từ vào hậu tố deque, cập nhật tiền tố
vô hiệu thêm(Tiền tố& tiền tố, hằng số chuỗi & s)
{
   nếu như (tiền tố.kích thước() == NPREF) {
     statetab[tiền tố].push_back(s);
     prefix.pop_front();
   }
   tiền tố.đẩy_lại(s);
}
 
// tạo: tạo ra đầu ra, một từ trên một dòng
vô hiệu phát ra( số nguyên từ n)
{
   Tiền tố tiền tố;
   số nguyên Tôi;
 
   vì (i = 0; i < NPREF; i++)
     thêm(tiền tố, KHÔNG PHẢI TỪ);
   vì (i = 0; i < n từ; i++) {
     vector& suf = statetab[tiền tố];
     hằng số chuỗi& w = suf[ rand () % suf.size()];
     nếu như (w == KHÔNG PHẢI TỪ)
       phá vỡ ;
     lệnh << w << "\N" ;
     prefix.pop_front(); // nâng cao
     tiền tố.đẩy_lại(w);
   }
}

4. chương trình c.

Nếu bạn cần chương trình chạy đủ nhanh thì nó chỉ có thể được triển khai bằng ngôn ngữ cấp thấp hơn. Khi chúng tôi triển khai nó bằng ngôn ngữ C, chúng tôi phải xem xét nhiều vấn đề khác nhau. Trước hết, vấn đề đầu tiên chúng ta gặp phải là làm thế nào để thể hiện mối quan hệ giữa tiền tố và hậu tố?

Mối quan hệ giữa tiền tố và hậu tố được lưu trữ ở đây bằng cách sử dụng khóa tiền tố và giá trị hậu tố. Chúng tôi biết rằng bảng băm có tốc độ tìm kiếm nhanh nhất nên sử dụng bảng băm ở đây là hợp lý. của nó. Tiền tố được sử dụng làm chìa khóa. Dựa trên những ý tưởng trên, nếu bạn cẩn thận hơn thì sẽ không có vấn đề gì lớn.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
/* Bản quyền (C) 1999 Lucent Technologies */
/* Trích từ 'Thực hành lập trình' */
/* của Brian W. Kernighan và Rob Pike */
 
/*
  * Trình tạo văn bản ngẫu nhiên chuỗi Markov.
  */
 
#include
#include
#include
#include
#include
#include "eprintf.h"
 
liệt kê {
   NPREF = 2,  /* số lượng từ tiền tố */
   NHASH = 4093, /* kích thước của mảng bảng băm trạng thái */
   TỐI ĐA = 10000 /* số từ tối đa được tạo ra */
};
 
định nghĩa kiểu cấu trúc Nhà nước Nhà nước;
định nghĩa kiểu cấu trúc Hậu tố Hậu tố;
 
cấu trúc Tình trạng { /* danh sách tiền tố + hậu tố */
   char  *pref[NPREF];  /* tiền tố từ */
   Hậu tố *suf;      /* danh sách các hậu tố */
   Trạng thái *tiếp theo;     /* tiếp theo trong bảng băm */
};
 
cấu trúc Hậu tố { /* danh sách các hậu tố */
   char  *từ;     /* hậu tố */
   Hậu tố *next;     /* tiếp theo trong danh sách hậu tố */
};
 
Trạng thái *tra cứu( char *tiền tố[], số nguyên tạo nên);
vô hiệu  xây dựng( char *tiền tố[], TÀI LIỆU *);
vô hiệu  phát ra( số nguyên từ);
vô hiệu  thêm vào( char *tiền tố[], char *từ);
 
Trạng thái *statetab[NHASH];  /* bảng băm của các trạng thái */
 
char KHÔNG TỪ[] = "\N" ; /* không thể xuất hiện như từ thực */
 
/* markov main: tạo văn bản ngẫu nhiên theo chuỗi markov */
số nguyên chủ yếu( vô hiệu )
{
   số nguyên tôi, nwords = MAXGEN;
   char *tiền tố[NPREF];    /* tiền tố đầu vào hiện tại */
 
   số nguyên c;
   dài hạt giống;
 
   đặt tên chương trình( "markov" );
   hạt giống = thời gian (VÔ GIÁ TRỊ);
 
   srand (hạt giống);
   vì (i = 0; i < NPREF; i++) /* thiết lập tiền tố ban đầu */
     prefix[i] = KHÔNG PHẢI TỪ;
   xây dựng(tiền tố, stdin);
   thêm(tiền tố, KHÔNG PHẢI TỪ);
   tạo ra(nwords);
   trở lại 0;
} 
 
hằng số số nguyên SỐ NHÂN = 31; /* cho hàm băm() */
 
/* băm: tính toán giá trị băm cho mảng các chuỗi NPREF */
chưa ký số nguyên băm( char *s[NPREF])
{
   chưa ký số nguyên h;
   chưa ký char *P;
   số nguyên Tôi;
 
   h = 0;
   vì (i = 0; i < NPREF; i++)
     vì (p = (không dấu char *) s[i]; *p != '\0' ; p++)
       h = HỆ SỐ * h + *p;
   trở lại h % NHASH;
}
 
/* tra cứu: tìm kiếm tiền tố; tạo nếu được yêu cầu. */
/* trả về con trỏ nếu có hoặc được tạo; NULL nếu không. */
/* việc tạo không strdup nên chuỗi không được thay đổi sau đó. */
Tra cứu trạng thái* char *tiền tố[NPREF], số nguyên tạo nên)
{
   số nguyên tôi, h;
   Trạng thái *sp;
 
   h = băm(tiền tố);
   vì (sp = statetab[h]; sp != NULL; sp = sp->next) {
     vì (i = 0; i < NPREF; i++)
       nếu như ( strcmp (tiền tố[i], sp->pref[i]) != 0)
         phá vỡ ;
     nếu như (tôi == NPREF)   /* tìm thấy nó */
       trở lại sp;
   }
   nếu như (tạo nên) {
     sp = (Trạng thái *) emalloc( kích thước của (Tình trạng));
     vì (i = 0; i < NPREF; i++)
       sp->pref[i] = tiền tố[i];
     sp->suf = NULL;
     sp->next = statetab[h];
     statetab[h] = sp;
   }
   trở lại sp;
}
 
/* addsuffix: thêm vào trạng thái. hậu tố không được thay đổi sau đó */
vô hiệu addsuffix(State *sp, char *hậu tố)
{
   Hậu tố *suf;
 
   suf = (Hậu tố *) emalloc( kích thước của (Hậu tố));
   suf->word = hậu tố;
   suf->tiếp theo = sp->suf;
   sp->suf =suf;
}
 
/* thêm: thêm từ vào danh sách hậu tố, cập nhật tiền tố */
vô hiệu thêm vào( char *tiền tố[NPREF], char *hậu tố)
{
   Trạng thái *sp;
 
   sp = tra cứu(tiền tố, 1); /* tạo nếu không tìm thấy */
   thêm hậu tố (sp, hậu tố);
   /* di chuyển các từ xuống tiền tố */
   ghi nhớ di chuyển (tiền tố, tiền tố+1, (NPREF-1)* kích thước của (tiền tố[0]));
   tiền tố[NPREF-1] = hậu tố;
}
 
/* xây dựng: đọc đầu vào, xây dựng bảng tiền tố */
vô hiệu xây dựng( char *tiền tố[NPREF], TÀI LIỆU *f)
{
   char buf[100], fmt[10];
 
   /* tạo một chuỗi định dạng; %s có thể tràn bộ đệm */
   chạy nước rút (fmt, "%%%%" , kích thước của (bổ sung)-1);
   trong khi ( fscanf (f, fmt, buf) != EOF)
     thêm(tiền tố, estrdup(buf));
}
 
/* tạo: tạo ra đầu ra, một từ trên một dòng */
vô hiệu phát ra( số nguyên từ n)
{
   Trạng thái *sp;
   Hậu tố *suf;
   char *tiền tố[NPREF], *w;
   số nguyên tôi, nmatch;
 
   vì (i = 0; i < NPREF; i++) /* thiết lập lại tiền tố ban đầu */
     prefix[i] = KHÔNG PHẢI TỪ;
 
   vì (i = 0; i < n từ; i++) {
     sp = tra cứu(tiền tố, 0);
     nếu như (sp == NULL)
       bản in điện tử "lỗi nội bộ: tìm kiếm không thành công" );
     nmatch = 0;
     vì (suf = sp->suf; suf != NULL; suf = suf->next)
       nếu như ( rand () % ++nmatch == 0) /* xác suất = 1/nmatch */
         w = suf->từ;
     nếu như (nmatch == 0)
       bản in điện tử "lỗi nội bộ: không có hậu tố %d %s" , i, tiền tố[0]);
     nếu như ( strcmp (w, KHÔNG PHẢI TỪ) == 0)
       phá vỡ ;
     inf ( "%s\n" , TRONG);
     ghi nhớ di chuyển (tiền tố, tiền tố+1, (NPREF-1)* kích thước của (tiền tố[0]));
     tiền tố[NPREF-1] = w;
   }
}

  。

Cuối cùng, bài viết này về mã triển khai ngôn ngữ awk, C++ và C của thuật toán chuỗi Markov (thuật toán markov) kết thúc tại đây. Nếu bạn muốn biết thêm về awk, C++ của thuật toán chuỗi Markov (thuật toán markov), Đối với nội dung mã triển khai ngôn ngữ C, vui lòng tìm kiếm các bài viết CFSDN hoặc tiếp tục duyệt các bài viết liên quan. Tôi hy vọng bạn sẽ ủng hộ blog của tôi trong tương lai! .

50 4 0
Đề xuất bài viết: Sửa script vbs của Gateway và DNS
Đề xuất bài viết: Phương pháp thực hiện thứ tự đảo ngược danh sách liên kết C++
Đề xuất bài viết: Chuyển đổi mã trong VBS hoặc ASP thành một dạng câu
Đề xuất bài viết: Phân tích các ví dụ sử dụng mẫu giao diện Facade trong lập trình mẫu thiết kế C++
qq735679552
Hồ sơ

Tôi là một lập trình viên xuất sắc, rất giỏi!

Nhận phiếu giảm giá taxi Didi miễn phí
Phiếu giảm giá taxi Didi
Các bài viết phổ biến trên toàn bộ trang web
Chứng chỉ ICP Bắc Kinh số 000000
Hợp tác quảng cáo: 1813099741@qq.com 6ren.com
Xem sitemap của VNExpress