Minggu, 25 April 2010
di
17.00
|
Kelompok
Qomarul Haryadi Irfan R. (07.04.111.00129)
Shodik (07.04.111.00147)
Tugas Keamanan Komputer
2. Jelaskan tentang DES!
Jawab :
Sejarah DES
• Algoritma DES dikembangkan di IBM dibawah kepemimpinan W.L. Tuchman pada tahun 1972. Algoritma ini didasarkan pada algoritma LUCIFER yang dibuat oleh Horst Feistel.
• Algoritma ini telah disetujui oleh National Bureau of Standard (NBS) setelah penilaian kekuatannya oleh National Security Agency (NSA) Amerika Serikat.
Tinjauan Umum
• DES termasuk ke dalam sistem kriptografi simetri dan tergolong jenis cipher blok.
• DES beroperasi pada ukuran blok 64 bit. DES mengenkripsikan 64 bit plainteks menjadi 64 bit cipherteks dengan menggunakan 56 bit kunci internal (internal key) atau upa-kunci (subkey). Kunci internal dibangkitkan dari kunci eksternal (external key) yang panjangnya 64 bit.
• Skema global dari algoritma DES adalah sebagai berikut (lihat Gambar 1):
1. Blok plainteks dipermutasi dengan matriks permutasi awal (initial permutation atau IP).
2. Hasil permutasi awal kemudian di-enciphering- sebanyak 16 kali (16 putaran). Setiap putaran menggunakan kunci internal yang berbeda.
3. Hasil enciphering kemudian dipermutasi dengan matriks permutasi balikan (invers initial permutation atau IP-1 ) menjadi blok cipherteks.
Plainteks
IP
16 kali Enciphering
IP-1
Cipherteks
Gambar 1. Skema Global Algoritma DES
• Di dalam proses enciphering, blok plainteks terbagi menjadi dua bagian, kiri (L) dan kanan (R), yang masing-masing panjangnya 32 bit. Kedua bagian ini masuk ke dalam 16 putaran DES.
• Pada setiap putaran i, blok R merupakan masukan untuk fungsi transformasi yang disebut f. Pada fungsi f, blok R dikombinasikan dengan kunci internal Ki. Keluaran dai fungsi f di-XOR-kan dengan blok L untuk mendapatkan blok R yang baru. Sedangkan blok L yang baru langsung diambil dari blok R sebelumnya. Ini adalah satu putaran DES.
Secara matematis, satu putaran DES dinyatakan sebagai
Li = Ri – 1
Ri = Li – 1 f(Ri – 1, Ki)
Gambar 2 memperlihatkan skema algoritma DES yang lebih rinci.
Gambar 2. Algoritma Enkripsi dengan DS
• Catatlah bahwa satu putaran DES merupakan model jaringan Feistel (lihat Gambar 3).
Gambar 3. Jaringan Feistel untuk satu putaran DES
• Perlu dicatat dari Gambar 2 bahwa jika (L16, R16) merupakan keluaran dari putaran ke-16, maka (R16, L16) merupakan pra-cipherteks (pre-ciphertext) dari enciphering ini. Cipherteks yang sebenarnya diperoleh dengan melakukan permutasi awal balikan, IP-1, terhadap blok pra-cipherteks.
Permutasi Awal
Sebelum putaran pertama, terhadap blok plainteks dilakukan permutasi awal (initial permutation atau IP). Tujuan permutasi awal adalah mengacak plainteks sehingga urutan bit-biit di dalamnya berubah. Pengacakan dilakukan dengan menggunakan matriks permutasi awal berikut ini:
58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7
Cara membaca tabel/matriks di atas: dua entry ujung kiri atas (58 dan 50) berarti:
“pindahkan bit ke-58 ke posisi bit 1”
“pindahkan bit ke-50 ke posisi bit 2”, dst
Pembangkitan Kunci Internal
• Karena ada 16 putaran, maka dibutuhkan kunci internal sebanyak 16 buah, yaitu K1, K2, …, K16. Kunci-kunci internal ini dapat dibangkitkan sebelum proses enkripsi atau bersamaan dengan proses enkripsi.
• Kunci internal dibangkitkan dari kunci eksternal yang diberikan oleh pengguna. Kunci eksternal panjangnya 64 bit atau 8 karakter.
• Misalkan kunci eksternal yang tersusun dari 64 bit adalah K.
Kunci eksternal ini menjadi masukan untuk permutasi dengan menggunakan matriks permutasi kompresi PC-1 sebagai berikut:
57 49 41 33 25 17 9 1 58 50 42 34 26 18
10 2 59 51 43 35 27 19 11 3 60 52 44 36
63 55 47 39 31 23 15 7 62 54 46 38 30 22
14 6 61 53 45 37 29 21 13 5 28 20 12 4
Dalam permutasi ini, tiap bit kedelapan (parity bit) dari delapan byte kunci diabaikan. Hasil permutasinya adalah sepanjang 56 bit, sehingga dapat dikatakan panjang kunci DES adalah 56 bit.
Selanjutnya, 56 bit ini dibagi menjadi 2 bagian, kiri dan kanan, yang masing-masing panjangnya 28 bit, yang masing-masing disimpan di dalam C0 dan D0:
C0: berisi bit-bit dari K pada posisi
57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18
10, 2, 59, 51, 43, 35, 27, 19, 11, 3, 60, 52, 44, 36
D0: berisi bit-bit dari K pada posisi
63, 55, 47, 39, 31, 23, 15, 7, 62, 54, 46, 38, 30, 22
14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 28, 20, 12, 4
Selanjutnya, kedua bagian digeser ke kiri (left shift) sepanjang satu atau dua bit bergantung pada tiap putaran. Operasi pergeseran bersifat wrapping atau round-shift. Jumlah pergeseran pada setiap putaran ditunjukkan pada Tabel 1 sbb:
Tabel 1. Jumlah pergeseran bit pada setiap putaran
Putaran, i Jumlah pergeseran bit
1 1
2 1
3 2
4 2
5 2
6 2
7 2
8 2
9 1
10 2
11 2
12 2
13 2
14 2
15 2
16 1
Misalkan (Ci, Di) menyatakan penggabungan Ci dan Di. (Ci+1, Di+1) diperoleh dengan menggeser Ci dan Di satu atau dua bit.
Setelah pergeseran bit, (Ci, Di) mengalami permutasi kompresi dengan menggunakan matriks PC-2 berikut:
14 17 11 24 1 5 3 28 15 6 21 10
23 19 12 4 26 8 16 7 27 20 13 2
41 52 31 37 47 55 30 40 51 45 33 48
44 49 39 56 34 53 46 42 50 36 29 32
Dengan permutasi ini, kunci internal Ki diturunkan dari (Ci, Di) yang dalam hal ini Ki merupakan penggabungan bit-bit Ci pada posisi:
14, 17, 11, 24, 1, 5, 3, 28, 15, 6, 21, 10
23, 19, 12, 4, 26, 8, 16, 7, 27, 20, 13, 2
dengan bit-bit Di pada posisi:
41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48
44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32
Jadi, setiap kunci internal Ki mempunyai panjang 48 bit.
Proses pembangkitan kunci-kunci internal ditunjukkan pada Gambar 4.
• Bila jumlah pergeseran bit-bit pada Tabel 1 dijumlahkan semuanya, maka jumlah seluruhnya sama dengan 28, yang sama dengan jumlah bit pada Ci dan Di. Karena itu, setelah putaran ke-16 akan didapatkan kembali C16 = C0 dan D16 = D0.
Gambar 4. Proses pembangkitan kunci-kunci internal DES
Enciphering
• Proses enciphering terhadap blok plainteks dilakukan setelah permutasi awal (lihat Gambar 1). Setiap blok plainteks mengalami 16 kali putaran enciphering (lihat Gambar 2). Setiap putaran enciphering merupakan jaringan Feistel yang secara matematis dinyatakan sebagai
Li = Ri – 1
Ri = Li – 1 f(Ri – 1, Ki)
Diagram komputasi fungsi f diperlihatkan pada Gambar 5.
Gambar 5. Rincian komputasi fungsi f
• E adalah fungsi ekspansi yang memperluas blok Ri – 1 yang panjangnya 32-bit menjadi blok 48 bit. Fungsi ekspansi direalisasikan dengan matriks permutasi ekspansi sbb:
32 1 2 3 4 5 4 5 6 7 8 9
8 9 10 11 12 13 12 13 14 15 16 17
16 17 18 19 20 21 20 21 22 23 24 25
24 25 26 27 28 29 28 29 30 31 32 1
• Selanjutnya, hasil ekpansi, yaitu E(Ri – 1), yang panjangnya 48 bit di-XOR-kan dengan Ki yang panjangnya 48 bit menghasilkan vektor A yang panjangnya 48-bit:
E(Ri – 1) Ki = A
• Vektor A dikelompokkan menjadi 8 kelompok, masing-masing 6 bit, dan menjadi masukan bagi proses substitusi. Proses substitusi dilakukan dengan menggunakan delapan buah kotak-S (S-box), S1 sampai S8. Setiap kotak-S menerima masukan 6 bit dan menghasilkan keluaran 4 bit. Kelompok 6-bit pertama menggunakan S1, kelompok 6-bit kedua menggunakan S2, dan seterusnya.
(cara pensubstitusian dengan kotak-S sudah dijelaskan pada materi “Prinsip-prinsip Perancangan Cipher Blok”)
Kedelapan kotak-S tersebut adalah:
S1:
14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
S2:
15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10
3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5
0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15
13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9
S3:
10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8
13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1
13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7
1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12
S4:
7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15
13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9
10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4
3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14
S5:
2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9
14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 16
4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14
11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3
S6:
12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11
10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8
9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6
4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13
S7:
4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1
13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6
1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2
6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12
S8:
13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7
1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2
7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8
2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11
• Keluaran proses substitusi adalah vektor B yang panjangnya 48 bit. Vektor B menjadi masukan untuk proses permutasi. Tujuan permutasi adalah untuk mengacak hasil proses substitusi kotak-S. Permutasi dilakukan dengan menggunakan matriks permutasi P (P-box) sbb:
16 7 20 21 29 12 28 17 1 15 23 26 5 8 31 10
2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25
• Bit-bit P(B) merupakan keluaran dari fungsi f.
• Akhirnya, bit-bit P(B) di-XOR-kan dengan Li – 1 untuk mendapatkan Ri (lihat Gambar 6):
Ri = Li – 1 P(B)
• Jadi, keluaran dari putaran ke-i adalah
(Li, Ri) = (Ri – 1 , Li – 1 P(B))
Gambar 6. Skema perolehan Ri
Permutasi Terakhir (Inverse Initial Permutation)
• Permutasi terakhir dilakukan setelah 16 kali putaran terhadap gabungan blok kiri dan blok kanan.
• Proses permutasi menggunakan matriks permutasi awal balikan (inverse initial permutation atau IP-1 ) sbb:
40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31
38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29
36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27
34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25
Dekripsi
• Proses dekripsi terhadap cipherteks merupakan kebalikan dari proses enkripsi. DES menggunakan algoritma yang sama untuk proses enkripsi dan dekripsi. Jika pada proses enkripsi urutan kunci internal yang digunakan adalah K1, K2, …, K16, maka pada proses dekripsi urutan kunci yang digunakan adalah K16, K15, …, K1.
• Untuk tiap putaran 16, 15, …, 1, keluaran pada setiap putaran deciphering adalah
Li = Ri – 1
Ri = Li – 1 f(Ri – 1, Ki)
yang dalam hal ini, (R16, L16) adalah blok masukan awal untuk deciphering. Blok (R16, L16) diperoleh dengan mempermutasikan cipherteks dengan matriks permutasi IP-1. Pra-keluaran dari deciphering adalah adalah (L0, R0). Dengan permutasi awal IP akan didapatkan kembali blok plainteks semula.
• Tinjau kembali proses pembangkitan kunci internal pada Gambar 4. Selama deciphering, K16 dihasilkan dari (C16, D16) dengan permutasi PC-2. Tentu saja (C16, D16) tidak dapat diperoleh langsung pada permulaan deciphering. Tetapi karena (C16, D16) = (C0, D0), maka K16 dapat dihasilkan dari (C0, D0) tanpa perlu lagi melakukan pergeseran bit. Catatlah bahwa (C0, D0) yang merupakan bit-bit dari kunci eksternal K yang diberikan pengguna pada waktu dekripsi.
• Selanjutnya, K15 dihasilkan dari (C15, D15) yang mana (C15, D15) diperoleh dengan menggeser C16 (yang sama dengan C0) dan D16 (yang sama dengan C0) satu bit ke kanan. Sisanya, K14 sampai K1 dihasilkan dari (C14, D14) sampai (C1, D1). Catatlah bahwa (Ci – 1, Di – 1) diperoleh dengan menggeser Ci dan Di dengan cara yang sama seperti pada Tabel 1, tetapi pergeseran kiri (left shift) diganti menjadi pergeseran kanan (right shift).
Mode DES
• DES dapat dioperasikan dengan mode ECB, CBC, OFB, dan CFB. Namun karena kesederhanaannya, mode ECB lebih sering digunakan pada paket program komersil meskipun sangat rentan terhadap serangan.
• Mode CBC lebih kompleks daripada EBC namun memberikan tingkat keamanan yang lebih bagus daripada mode EBC. Mode CBC hanya kadang-kadang saja digunakan.
Implementasi Hardware dan Software DES
• DES sudah diimplementasikan dalam bentuk perangkat keras.
• Dalam bentuk perangkat keras, DES diimplementasikan di dalam chip. Setiap detik chip ini dapat mengenkripsikan 16,8 juta blok (atau 1 gigabit per detik).
• Implementasi DES ke dalam perangkat lunak dapat melakukan enkripsi 32.000 blok per detik (pada komputer mainframe IBM 3090).
Keamanan DES
• Isu-isu yang menjadi perdebatan kontroversial menyangkut keamanan DES:
1. Panjang kunci
2. Jumlah putaran
3. Kotak-S
Panjang kunci
• Panjang kunci eksternal DES hanya 64 bit atau 8 karakter, itupun yang dipakai hanya 56 bit. Pada rancangan awal, panjang kunci yang diusulkan IBM adalah 128 bit, tetapi atas permintaan NSA, panjang kunci diperkecil menjadi 56 bit. Alasan pengurangan tidak diumumkan.
• Tetapi, dengan panjang kunci 56 bit akan terdapat 256 atau 72.057.594.037.927.936 kemungkinan kunci. Jika diasumsikan serangan exhaustive key search dengan menggunakan prosesor paralel mencoba setengah dari jumlah kemungkinan kunci itu, maka dalam satu detik dapat dikerjakan satu juta serangan. Jadi seluruhnya diperlukan 1142 tahun untuk menemukan kunci yang benar.
• Tahun 1998, Electronic Frontier Foundation (EFE) merancang dan membuat perangkat keras khusus untuk menemukan kunci DES secara exhaustive search key dengan biaya $250.000 dan diharapkan dapat menemukan kunci selama 5 hari. Tahun 1999, kombinasi perangkat keras EFE dengan kolaborasi internet yang melibatkan lebih dari 100.000 komputer dapat menemukan kunci DES kurang dari 1 hari.
Jumlah putaran
• Sebenarnya, delapan putaran sudah cukup untuk membuat cipherteks sebagai fungsi acak dari setiap bit plainteks dan setiap bit cipherteks. Jadi, mengapa harus 16 kali putaran?
• Dari penelitian, DES dengan jumlah putaran yang kurang dari 16 ternyata dapat dipecahkan dengan known-plaintext attack lebih mangkus daripada dengan brute force attack.
Kotak-S
• Pengisian kotak-S DES masih menjadi misteri tanpa ada alasan mengapa memilih konstanta-konstanta di dalam kotak itu.
Kunci Lemah dan Kunci Setengah Lemah
• DES mempunyai beberapa kunci lemah (weak key). Kunci lemah menyebabkan kunci-kunci internal pada setiap putaran sama (K1 = K2 = … = K16). Akibatnya, enkripsi dua kali berturut-turut terhadap plainteks menghasilkan kembali plainteks semula.
• Kunci lemah terjadi bila bit-bit di dalam Ci dan Di semuanya 0 atau 1, atau setengah dari kunci seluruh bitnya 1 dan setengah lagi seluruhnya 0.
• Kunci eksternal (dalam notasi HEX) yang menyebabkan terjadinya kunci lemah adalah (ingat bahwa setiap bit kedelapan adalah bit paritas).
Kunci lemah (dengan bit paritas) Kunci sebenarnya
0101 0101 0101 0101 0000000 0000000
1F1F 1F1F 1F1F 1F1F 0000000 FFFFFFF
E0E0 E0E0 F1F1 F11F FFFFFFF 0000000
FEFE FEFE FEFE FEFE FFFFFFF FFFFFFF
• Selain kunci lemah, DES juga mempunyai sejumlah pasangan kunci setengah-lemah (semiweak key). Pasangan kunci setengah- lemah mengenkripsikan plainteks menjadi cipherteks yang sama. Sehingga, satu kunci dalam pasangan itu dapat mendekripsi pesan yang dienkripsi oleh kunci yang lain di dalam pasangan itu.
• Kunci setengah-lemah terjadi bila:
1. Register C dan D berisi bit-bit dengan pola 0101…0101 atau 1010…1010
2. Register yang lain (C atau D) berisi bit-bit dengan pola 0000…0000, 1111…1111, 0101…0101, atau 1010…1010
• Ada 6 pasang kunci setengah lemah (dalam notasi HEX):
a. 01FE 01FE 01FE 01FE dan FE01 FE01 FE01 FE01
b. 1FE0 1FE0 0EF1 0EF1 dan E01F E01F F10E F10E
c. 01E0 01E0 01F1 01F1 dan E001 E001 F101 F101
d. 1FFE 1FFE 0EFE 0EFE dan FE1F FE1F FE0E FE0E
e. 011F 011F 010E 010E dan 1F01 1F01 0E01 0E01
f. E0FE E0FE F1FE F1FE dan FEE0 FEE0 FEF1 FEF1
1. Produk – produk Kerberos
• ProdFreeBSD
• Apple Mac OS X
• Red Hat Enterprise Linux 4
• Sun Solaris
• IBM AIX
• HP OpenVMS
2. Penyedia (CA) X.509
• Verisign
• OpenCA1
• ITU-T
• WSE 3.0
Diposting oleh
Zaoldyek Hunter Modunk
Label:
Keamanan Komputer
Tugas Keamanan Komputer
Qomarul Haryadi Irfan R
07.04.1.1.1.00129
1. Kerberos
Kerberos pertama kali dikembangkan pada dekade 1980-an sebagai sebuah metode untuk melakukan autentikasi terhadap pengguna dalam sebuah jaringan yang besar dan terdistribusi. Kerberos menggunakan enkripsi kunci rahasia/kunci simetris dengan algoritma kunci yang kuat sehingga klien dapat membuktikan identitas mereka kepada server dan juga menjamin privasi dan integritas komunikasi mereka dengan server. Protokol ini dinamai Kerberos, karena memang Kerberos (atau Cerberus) merupakan seekor anjing berkepala tiga (protokol Kerberos memiliki tiga subprotokol) dalam mitologi Yunani yang menjadi penjaga Tartarus, gerbang menuju Hades (atau Pluto dalam mitologi Romawi). BY.Menix akbar.
Kerberos adalah protokol otentikasi jaringan komputer, yang memungkinkan node berkomunikasi melalui jaringan tidak aman untuk membuktikan identitas mereka satu sama lain dengan cara yang aman.
Ini juga merupakan suite dari perangkat lunak bebas yang diterbitkan oleh Massachusetts Institute of Technology (MIT) yang mengimplementasikan protokol ini. Its desainer ditujukan pada model client-server, dan menyediakan otentikasi timbal balik - baik pengguna dan server memverifikasi identitas masing-masing. pesan protokol Kerberos dilindungi menghadapi eavesdropping dan replay serangan.
Kerberos dibangun pada kriptografi kunci simetris dan membutuhkan pihak ketiga yang terpercaya. Ekstensi untuk Kerberos dapat menyediakan untuk penggunaan kriptografi kunci publik selama fase-fase tertentu otentikasi.
Kerberos menggunakan sebagai dasar Protokol Needham-Schroeder simetris. Itu membuat penggunaan pihak ketiga yang terpercaya, disebut pusat distribusi kunci (KDC), yang terdiri dari dua bagian yang terpisah secara logis: sebuah Authentication Server (AS) Tiket Pemberian dan Server (TGS). Kerberos bekerja atas dasar "tiket" yang berfungsi untuk membuktikan identitas pengguna.
The KDC memelihara sebuah database kunci rahasia; setiap entitas pada jaringan - apakah klien atau server - saham kunci rahasia yang hanya diketahui oleh dirinya sendiri dan ke KDC. Pengetahuan tentang kunci ini berfungsi untuk membuktikan identitas suatu entitas. Untuk komunikasi antara dua entitas, yang KDC menghasilkan kunci sesi yang mereka dapat gunakan untuk mengamankan interaksi mereka. Keamanan protokol bergantung pada peserta mempertahankan sinkron longgar waktu dan pernyataan singkat keaslian Kerberos disebut tiket.
Protokol Kerberos memiliki tiga subprotokol agar dapat melakukan aksinya:
• Authentication Service (AS) Exchange: yang digunakan oleh Key Distribution Center (KDC) untuk menyediakan Ticket-Granting Ticket (TGT) kepada klien dan membuat kunci sesi logon.
• Ticket-Granting Service (TGS) Exchange: yang digunakan oleh KDC untuk mendistribusikan kunci sesi layanan dan tiket yang diasosiasikan dengannya.
• Client/Server (CS) Exchange: yang digunakan oleh klien untuk mengirimkan sebuah tiket sebagai pendaftaran kepada sebuah layanan.
Sesi autentikasi Kerberos yang dilakukan antara klien dan server adalah sebagai berikut:
Cara kerja protokol Kerberos
1. Informasi pribadi pengguna dimasukkan ke dalam komputer klien Kerberos, yang kemudian akan mengirimkan sebuah request terhadap KDC untuk mengakses TGS dengan menggunakan protokol AS Exchange. Dalam request tersebut terdapat bukti identitas pengguna dalam bentuk terenkripsi.
2. KDC kemudian menerima request dari klien Kerberos, lalu mencari kunci utama (disebut sebagai Master Key) yang dimiliki oleh pengguna dalam layanan direktori Active Directory (dalam Windows 2000/Windows Server 2003) untuk selanjutnya melakukan dekripsi terhadap informasi identitas yang terdapat dalam request yang dikirimkan. Jika identitas pengguna berhasil diverifikasi, KDC akan meresponsnya dengan memberikan TGT dan sebuah kunci sesi dengan menggunakan protokol AS Exchange.
3. Klien selanjutnya mengirimkan request TGS kepada KDC yang mengandung TGT yang sebelumnya diterima dari KDC dan meminta akses tehradap beberapa layanan dalam server dengan menggunakan protokol TGS Exchange.
4. KDC selanjutnya menerima request, malakukan autentikasi terhadap pengguna, dan meresponsnya dengan memberikan sebuah tiket dan kunci sesi kepada pengguna untuk mengakses server target dengan menggunakan protokol TGS Exchange.
5. Klien selanjutnya mengirimkan request terhadap server target yang mengandung tiket yang didapatkan sebelumnya dengan menggunakan protokol CS Exchange. Server target kemudian melakukan autentikasi terhadap tiket yang bersangkutan, membalasnya dengan sebuah kunci sesi, dan klien pun akhirnya dapat mengakses layanan yang tersedia dalam server.
Meski terlihat rumit, pekerjaan ini dilakukan di balik layar, sehingga tidak terlihat oleh pengguna.
2. X.509
Dalam sistem X.509, sebuah Sertifikasi Authority masalah sertifikat mengikat kunci publik ke Nama Distinguished tertentu dalam tradisi X.500, atau ke Nama Alternatif seperti alamat e-mail atau DNS-entry.
Sertifikat terpercaya Sebuah organisasi akar dapat didistribusikan kepada seluruh karyawan sehingga mereka dapat menggunakan sistem perusahaan PKI. Browser seperti Internet Explorer, Netscape / Mozilla, Opera, Safari dan Chrome datang dengan sertifikat akar pra-instal, jadi sertifikat SSL dari vendor besar akan bekerja langsung; yang berlaku pengembang browser 'menentukan CA dipercaya pihak ketiga untuk browser' pengguna.
X.509 juga meliputi standar untuk daftar sertifikat pembatalan (CRL) implementasi, suatu aspek yang sering diabaikan sistem PKI. Cara IETF-disetujui untuk memeriksa validitas sertifikat adalah Online Certificate Status Protocol (OCSP). Firefox 3 memungkinkan pengecekan OCSP secara default bersama dengan versi Windows termasuk Vista dan kemudian.
3. Protokol simetris
Istilah Needham-Schroeder protokol dapat mengacu pada salah satu dari dua protokol komunikasi yang diharapkan untuk menggunakan suatu jaringan tidak kuat, kedua-duanya yang diusulkan oleh Needham Dan Michael Schroeder :
• Needham-Schroeder Protokol Kunci Symmetric didasarkan pada suatu encryption algoritma symmetric. [Itu] membentuk basis [itu] untuk [itu] Kerberos protokol. Protokol ini mengarahkan untuk menetapkan suatu sesi menyetem antar[a] dua pesta pada [atas] suatu jaringan, [yang] secara khas untuk melindungi komunikasi lebih lanjut.
• Needham-Schroeder Public-Key Protokol, public-key ilmu membaca sandi yang didasarkan pada. Protokol ini dimaksudkan untuk menyediakan pengesahan timbal balik antar[a] dua pesta yang berkomunikasi pada [atas] suatu jaringan, tetapi dalam format diusulkan nya adalah tidak kuat.
4. Public Key Infrastructure (PKI)
Public Key Infrastructure (PKI) adalah satu set perangkat keras, perangkat lunak, orang, kebijakan, dan prosedur yang diperlukan untuk membuat, mengelola, mendistribusikan, menggunakan, menyimpan, dan mencabut sertifikat digital. Dalam kriptografi, sebuah PKI adalah pengaturan yang mengikat kunci publik dengan identitas masing-masing pengguna melalui otoritas sertifikat (CA). Identitas pengguna harus unik dalam setiap domain CA. Pengikatan dibentuk melalui proses registrasi dan penerbitan, yang, tergantung pada tingkat pengikatan jaminan memiliki, dapat dilakukan oleh perangkat lunak pada CA, atau di bawah pengawasan manusia. Peran PKI yang menjamin mengikat ini disebut Otorita Pendaftaran (RA). Untuk setiap pengguna, identitas pengguna, kunci publik, kondisi yang mengikat mereka validitas, dan atribut lainnya yang dibuat unforgeable dalam sertifikat kunci publik yang dikeluarkan oleh CA.
Istilah ini dipercaya pihak ketiga (TTP) juga dapat digunakan untuk otoritas sertifikat (CA). Istilah PKI kadang-kadang keliru digunakan untuk menunjukkan algoritma kunci publik, yang tidak memerlukan penggunaan CA.
Secara umum, ada tiga pendekatan untuk mendapatkan kepercayaan ini: Otoritas Sertifikat (CA), Web dari Trust (WOT), dan infrastruktur Wikipedia kunci publik (SPKI).
5. Public key certificate
Dalam kriptografi, sertifikat kunci publik (juga dikenal sebagai sertifikat digital atau sertifikat identitas) adalah dokumen elektronik yang menggunakan tanda tangan digital untuk mengikat kunci publik dengan identitas - informasi seperti nama orang atau organisasi, mereka alamat, dan sebagainya. Sertifikat ini dapat digunakan untuk memverifikasi bahwa kunci publik milik individu.
Dalam infrastruktur utama khas publik (PKI) skema, tanda tangan akan dari otoritas sertifikat (CA). Dalam web skema kepercayaan, signature-nya baik pengguna (sertifikat ditandatangani sendiri) atau pengguna lain ("dukungan"). Dalam kedua kasus, tanda tangan pada sertifikat yang attestations oleh penandatangan sertifikat bahwa informasi identitas dan kunci publik milik bersama.
Untuk keamanan dibuktikan ini ketergantungan pada sesuatu di luar sistem tersebut memiliki konsekuensi bahwa setiap skema sertifikasi kunci publik harus bergantung pada beberapa asumsi konfigurasi khusus, seperti adanya otoritas sertifikat.
Sertifikat dapat dibuat untuk server berbasis Unix dengan alat seperti OpenSSL's ssl-ca. atau gensslcert SuSE's. Ini dapat digunakan untuk menerbitkan sertifikat unmanaged, Sertifikasi Authority (CA) sertifikat untuk mengelola sertifikat lainnya, dan pengguna dan / atau permintaan komputer sertifikat harus ditandatangani oleh CA, serta sejumlah sertifikat fungsi-fungsi terkait.
Diposting oleh
Zaoldyek Hunter Modunk
Label:
Keamanan Komputer
tugas individu STBI part2
Resume
buku Christopher D. Manning, Prabhakar Raghavan, Hinrich Schütze teks 4 dan teks 6
Konstruksi Index
Dalam bab ini, kita melihat bagaimana membangun sebuah indeks terbalik. Kami akan memanggil proses konstruksi indeks atau pengindeksan dan proses atau mesin yang melaksanakan pengindeksan. Rancangan algoritma pengindeksan diatur oleh batasan hardware. Oleh karena itu kita akan memulai bab ini dengan tinjauan dasar-dasar perangkat keras komputer yang relevan untuk pengindeksan. Kami kemudian memperkenalkan semacam berbasis pengindeksan yang diblokir, sebuah mesin tunggal algoritma yang efisien yang dirancang untuk statis koleksi yang dapat dilihat sebagai yang lebih scalable. Untuk koleksi yang sangat besar seperti web, pengindeksan harus didistribusikan melalui kelompok komputer dengan ratusan atau ribuan mesin. Akhirnya, kita akan membahas beberapa komplikasi yang dapat timbul dalam pengindeksan. Seperti keamanan dan indeks untuk pengambilan peringkat. Dalam pencarian web, dokumen tidak pada sistem file lokal, tapi harus spider atau merangkak. Di pencarian perusahaan, sebagian besar dokumen yang terangkum dalam manajemen konten bervariasi sistem, aplikasi email dan database. Sementara sebagian besar aplikasi ini dapat diakses melalui http, API biasanya lebih efisien. Pembaca harus menyadari bahwa bangunan sub-sistem yang berupa teks mentah untuk proses pengindeksan dapat dengan sendirinya menjadi masalah yang menantang.
Dasar Hardware
Banyak keputusan ketika membangun sebuah sistem pencarian informasi yang didasarkan pada karakteristik dari sistem perangkat keras komputer. Karena itu kita memulai bab ini dengan tinjauan singkat perangkat keras komputer. Sebuah dasar daftar hardware yang akan kita butuhkan dalam pembahasan ini untuk memotivasi sistem IR desain berikut.
• Akses ke data dalam memori jauh lebih cepat daripada akses data pada disk. Ini mengambil beberapa clock cycle (mungkin 5 × 10-9 detik) untuk mengakses byte memori, tetapi lebih lama untuk transfer dari disk (sekitar 2 × 10-8 detik). Akibatnya, kita ingin menyimpan data sebanyak mungkin dalam memori, terutama data yang sering kita butuhkan untuk mengakses. Kita sebut teknik yang sering digunakan menyimpan data disk caching dalam cache memori utama.
• Ketika melakukan sebuah disk membaca atau menulis, butuh beberapa saat untuk disk head untuk pindah ke bagian disk tempat data berada. Kali ini disebut mencari waktu dan ini adalah tentang 5ms pada umumnya rata-rata untuk disk. Tidak ada data sedang ditransfer selama mencari. Dalam rangka untuk memaksimalkan transfer data bunga, potongan data yang akan dibaca harus disimpan pada disk. Sebagai contoh, menggunakan angka-angka pada Tabel 4.1 hal itu mungkin memakan waktu sedikitnya 0,2 detik untuk mentransfer 10 MB dari disk ke memori jika disimpan sebagai salah satu bongkahan, tetapi sampai 0.2 + 100 × (5 × 10-3) = 0,7 detik jika disimpan dalam 100 non-contiguous bongkahan karena kita perlu memindahkan disk kepala sampai dengan 100 kali.
• Sistem operasi umumnya membaca dan menulis seluruh blok. Dengan demikian, membaca
satu byte dari disk dapat mengambil waktu sebanyak membaca seluruh blok. Ukuran blok dari 8 KB, 16 KB, 32 KB dan 64 KB yang umum.
• Data transfer dari disk ke memory akan ditangani oleh systembus, bukan oleh prosesor. Ini berarti bahwa prosesor yang tersedia untuk memproses data saat disk I / O. Kita dapat memanfaatkan fakta ini untuk mempercepat transfer data dengan dikompresi menyimpan data pada disk. Dengan asumsi yang efisien dekompresi algoritma, total waktu membaca dan kemudia dikompresi data biasanya kurang daripada membaca data yang tidak dikompresi.
• Server yang digunakan dalam sistem IR biasanya memiliki beberapa GB memori utama, kadang-kadang puluhan GB. Ruang disk yang tersedia adalah beberapa kali lipat lebih besar.
Blocked sort-based indexing
Pertama-tama membuat perakitan koleksi semua docID istilah-pasangan. Kemudian menyortir pasangan dengan istilah sebagai kunci dominan dan docID sebagai kunci sekunder. Akhirnya, kami mengatur untuk setiap docIDs istilah ke daftar posting dan menghitung statistik seperti frekuensi term dan dokumen. Untuk koleksi yang kecil, semua ini dapat dilakukan di memori. Kami akan menjelaskan metode untuk koleksi besar yang memerlukan penggunaan sekunder penyimpanan. Untuk membuat pembangunan index lebih efisien, kami mewakili istilah termIDs, di mana masing-masing adalah unik termID nomor seri. Kita dapat membangun pemetaan dari istilah ke termIDs on the fly sementara kami memproses koleksi, dalam dua pendekatan lulus, kami menyusun kosakata pertama dan membangun indeks terbalik. Algoritma konstruksi indeks yang dijelaskan dalam bab ini melewati satu data. Jika ukuran file antara selama indeks konstruksi dalam faktor kecil memori yang tersedia, maka teknik kompresi dapat membantu; tetapi banyak koleksi file posting yang besar tidak bisa masuk ke dalam memori bahkan setelah kompresi. Dengan memori utama tidak mencukupi, kita perlu menggunakan algoritma sorting eksternal. Untuk dapat diterima kecepatan, persyaratan pusat algoritma semacam itu adalah bahwa hal itu meminimalkan jumlah random disk yang mencari selama sequential pemilahan disk dibaca jauh lebih cepat daripada mencari seperti yang kita jelaskan sebelumnya. Salah satu solusinya adalah blocked sort-berbasis algoritma pengindeksan atau BSBI pada Gambar 4.2. BSBI (i) segmen koleksi menjadi beberapa bagian dengan ukuran yang sama, (ii) memilah termID pasang docID setiap bagian dalam memori, (iii) toko intermediate diurutkan hasilnya pada disk dan (iv) gabungan semua hasil menengah ke dalam akhir indeks.
Algoritma memparsing dokumen ke termID-docID dan mengakumulasi pasangan
pasangan dalam memory sampai blok ukuran tetap penuh pada Gambar 4.2. Kami memilih ukuran blok untuk menyesuaikan dengan nyaman ke dalam memori untuk
izin yang cepat dalam-memori semacam itu. Blok ini kemudian dibalik dan ditulis ke disk.
Inversi melibatkan dua langkah. Pertama kita menyortir pasangan termID-inversi docID. Berikutnya kami kumpulkan semua termID-docID berpasangan dengan termID yang sama ke dalam daftar posting, dimana posting hanyalah sebuah docID. Hasilnya, indeks terbalik untuk blok baru saja kita baca, kemudian ditulis ke disk.
Single-pass di memori pengindeksan
Blocked sort berbasis skala pengindeksan memiliki sifat yang sangat baik. Untuk koleksi yang sangat besar, struktur data ini tidak muat ke dalam memori. Alternatif yang lebih scalable adalah
single-pass di memori atau SPIMI pengindeksan. SPIMI dapat mengindeks koleksi dari berbagai ukuran asalkan ada cukupruang disk yang tersedia. SPIMI-invert disebut berulang pada token sungai sampai seluruh koleksi telah diproses. Token diproses satu per satu. Ketika sebuah istilah terjadi untuk pertama kali, itu akan ditambahkan ke kamus, dan daftar posting baru diciptakan. Perbedaan antara BSBI dan SPIMI adalah bahwa SPIMI menambahkan posting langsung
ke daftar posting. Daripada pertama mengumpulkan semua pasangan termID-docID
kemudian menyortir mereka (seperti yang kita lakukan di BSBI), masing-masing daftar posting adalah dinamis dan akan segera tersedia untuk mengumpulkan posting. Ini memiliki dua keuntungan. Hal ini akan menghemat memori karena kita melacak istilah milik sebuah daftar posting, sehingga termIDs dari posting tidak perlu disimpan. Sebagai hasilnya, indeks proses pembangunan secara keseluruhan lebih efisien.
Distributed pengindeksan
Koleksi sering begitu besar sehingga kita tidak dapat melakukan konstruksi indeks yang efisien
pada satu mesin. Hal ini terutama berlaku dari World Wide Web dimana kita membutuhkan komputer yang besar untuk membangun apapun. Oleh karena itu mesin pencari web didistribusikan menggunakan algoritma pengindeksan untuk indeks konstruksi. Hasil dari proses pembangunan adalah indeks yang didistribusikan terbagi di beberapa mesin, baik menurut istilah atau sesuai dengan dokumen. Inti dari sebuah cluster adalah memecahkan masalah komputasi besar komoditas murah mesin atau node yang dibangun dari standar bagian (prosesor, memori, disk) sebagai lawan pada sebuah super komputer dengan perangkat keras khusus. Sementara ratusan atau ribuan dari mesin tersedia dalam kelompok-kelompok seperti itu, mesin bisa gagal setiap waktu. Satu persyaratan untuk mengindeks terdistribusi kuat karena itu yang kita
membagi pekerjaan ke dalam potongan-potongan yang kita dapat dengan mudah menetapkan dan - dalam kasus failure - menugaskan kembali.
Pengindeksan dynamic
Istilah-istilah baru perlu ditambahkan ke dalam kamus, dan daftar posting perlu diperbarui untuk istilah-istilah yang ada. Cara paling mudah untuk mencapai ini adalah dengan merekonstruksi secara berkala indeks dari nol. Ini adalah solusi yang baik jika sejumlah perubahan dari waktu ke waktu adalahkecil dan penundaan dalam membuat dokumen baru dicari dapat diterima, dan
jika cukup banyak sumber daya yang tersedia untuk membangun indeks baru sementara yang lama masih tersedia untuk query. Sebuah indeks dan largemain indeks tambahan kecil
yang menyimpan dokumen baru. Indeks auxiliary disimpan di dalam memori. Pencarian
dijalankan di kedua indeks dan hasil penggabungan. Penghapusan disimpan dalam sebuah penghapusan bit vektor. Kita dapat menyaring dokumen dihapus sebelum kembali
hasil pencarian. Dokumen diperbarui dengan menghapus dan memasukkan kembali dokumen tersebut.
.
Jenis indeks
Algoritma yang dibahas di sini semua bisa diterapkan untuk posisi indeks. Dalam indeks kita telah mempertimbangkan sejauh ini, daftar posting diperintahkan dengan terhadap docID. Hal ini menguntungkan untuk kompresi - docIDs bukannya lebih kecil kita dapat menekan kesenjangan antara ID, sehingga mengurangi kebutuhan ruang untuk indeks. Namun, struktur ini
untuk indeks tidak optimal ketika kita membangun peringkat peringkat Retrieval, dibandingkan dengan sistem pengambilan Boolean. Dalam peringkat pencarian, posting sering disusun berdasarkan berat badan atau dampak, dengan bobot tertinggi posting pertama terjadi. Dengan susunan ini, scanning postingan daftar selama pemrosesan query biasanya dapat dihentikan lebih awal ketika beban telah menjadi begitu kecil sehingga dokumen lebih lanjut dapat diperkirakan dari rendah kesamaan dengan query.
Skor, Istilah Bobot dan Model Ruang Vector
Sejauh ini kita telah berurusan dengan indeks yang mendukung Boolean queries. Dalam kasus koleksi dokumen besar, jumlah hasil dokumen yang sesuai dapat jauh melebihi jumlah pengguna manusia yang bisa menyaring. Oleh karena itu, penting untuk sebuah mesin pencari untuk menentukan peringkat-memesan pencocokan dokumen permintaan. Bab ini terdiri dari tiga ide pokok :
1. Kami memperkenalkan parametrik dan zona indeks, yang berfungsi
dua tujuan. Pertama, mereka memungkinkan kita untuk mengindeks dan mengambil dokumen oleh metadata seperti bahasa di mana sebuah dokumen yang tertulis. Kedua,
mereka memberi kita sarana untuk penilaian sederhana (dan dengan demikian peringkat) dokumen sebagai tanggapan atas permintaan.
2. Selanjutnya, kita mengembangkan gagasan bobot pentingnya istilah dalam dokumen, berdasarkan statistik terjadinya istilah.
3. Setelah itu kami menunjukkan bahwa dengan melihat setiap dokumen sebagai vektor seperti berat, kita dapat menghitung skor antara permintaan dan setiap dokumen.
Pandangan ini dikenal sebagai ruang vektor mencetak gol.
Parametric dan zona indeks
Sebagian besar dokumen memiliki struktur tambahan. Umumnya dokumen digital menyandi,
mesin dikenali dalam bentuk, metadata tertentu yang terkait MET dengan setiap dokumen.
Dengan metadata, kita berarti bentuk-bentuk khusus data tentang dokumen, seperti
sebagai penulis (s), judul dan tanggal publikasi. Metadata ini akan umumnya meliputi bidang-bidang seperti tanggal penciptaan dan format dokumen, baik penulis dan mungkin judul dokumen.
Pertimbangkan pertanyaan dari form "menemukan dokumen yang ditulis oleh WilliamShakespeare pada tahun 1601, yang berisi frase sayangnya Yorick miskin ". Pemrosesan query kemudian seperti biasa terdiri dari posting persimpangan, kecuali bahwa kita dapat menggabungkan posting dari standar terbalik serta indeks parametrik. Ada satu parametric indeks untuk masing-masing bidang; hal itu memungkinkan kita untuk memilih hanya
pencocokan dokumen tanggal yang ditentukan dalam pencarian.
Zona mirip dengan bidang, kecuali isi zona dapat berupa teks bebas. Sedangkan lapangan mungkin diperlukan waktu yang relatif kecil pada seperangkat nilai, zona dapat dianggap sebagai sewenang-wenang, jumlah teks terbatas. Misalnya, judul dan abstrak dokumen umumnya diperlakukan sebagai zona. Kita mungkin membangun sebuah indeks terbalik terpisah untuk setiap zona dari sebuah dokumen, untuk mendukung permintaan tersebut sebagai "menemukan dokumen dengan pedagang di judul dan william dalam daftar penulis dan ungkapan hujan lembut di dalam tubuh ". Hal ini memiliki efek membangun indeks. Sedangkan dalam kamus untuk indeks parametric berasal dari kosakata yang tetap (himpunan bahasa, atau set tanggal), yang kamus untuk indeks zona struktur harus kosa kata apa pun yang berasal dari
teks zona itu.
Berat zona scoring
Kita telah berfokus pada pengambilan dokumen berdasarkan Boolean query di ladang dan zona. Kita sekarang beralih ke aplikasi kedua zona dan ladang. Boolean query diberi q dan sebuah dokumen d zona tertimbang menetapkan skor ke pasangan (q, d) suatu nilai dalam interval [0, 1], dengan menghitung kombinasi linear zona nilai, di mana setiap zona dokumen menyumbangkan Boolean nilai. Lebih khusus lagi, pertimbangkan satu set dokumen masing-masing memiliki ℓ
zona. Biarkan g1,. . . , G ℓ ∈ [0, 1] sehingga ℓ å i = 1 gi = 1. Untuk 1 ≤ i ≤ ℓ, biarkan si menjadi
Nilai boolean yang menunjukkan pertandingan (atau ketiadaan daripadanya) antara q dan engan
zona. Misalnya, nilai Boolean dari zona bisa 1 jika semua permintaan istilah (s) yang terjadi di zona itu, dan nol sebaliknya; memang, itu bisa setiap Boolean fungsi yang memetakan kehadiran istilah permintaan dalam zona ke 0, 1. Kemudian, zona skor tertimbang didefinisikan sebagai
ZONESCORE (Q1, q2)
1 float nilai [N] = [0]
2 konstan g [ℓ]
3 p1 ← postingan lama (Q1)
4 p2 ← postingan lama (q2)
5 / / nilai [] adalah sebuah array dengan skor entri untuk setiap dokumen, diinisialisasi ke nol.
6 / / p1 dan p2 adalah diinisialisasi agar menunjuk ke awal masing-masing posting.
7 / / Asumsikan g [] adalah untuk melakukan masing-masing zona bobot.
8 sementara p1 6 = NIL dan p2 6 = NIL
9 lakukan jika docID (p1) = docID (p2)
10 maka skor [docID (p1)] ← WEIGHTEDZONE (p1, p2, g)
11 p1 ← berikutnya (p1)
12 p2 ← berikutnya (p2)
13 else if docID (p1) Belajar beban
Bagaimana kita menentukan bobot tertimbang gi untuk zona scoring? Bobot ini dapat ditentukan oleh seorang ahli (atau, pada prinsipnya, user); namun semakin, bobot ini adalah "belajar" dengan menggunakan contoh-contoh pelatihan yang telah dinilai editorial. Metodologi yang terakhir ini berada di bawah kelas umum pendekatan untuk penilaian dan peringkat dalam pencarian informasi, yang dikenal sebagai mesin-belajar relevansi. Kami menyediakan pengenalan singkat dengan topik ini di sini karena zona tertimbang mencetak menyajikan pengaturan yang bersih untuk memperkenalkan itu; sebuah lengkap tuntutan perkembangan pemahaman pembelajaran mesin.
Sejauh ini, skor telah bergantung pada apakah atau tidak istilah query hadir dalam
zona dalam dokumen. Kami mengambil langkah logis berikutnya: sebuah dokumen atau
zona yang menyebutkan istilah query lebih sering lebih berkaitan dengan permintaan
dan karenanya harus menerima skor yang lebih tinggi. Untuk memotivasi ini, kita mengingat
pengertian tentang permintaan teks bebas diperkenalkan sebelumnya: query di mana
persyaratan query diketik ke dalam bentuk yang unik antarmuka pencarian, tanpa
menghubungkan operator pencarian (seperti Boolean operator). Query ini gaya, yang sangat populer di Web, pandangan query hanya sebagai kumpulan kata-kata. Sebuah mekanisme penilaian yang masuk akal maka adalah untuk menghitung skor. Singkatnya, di atas istilah permintaan, skor pertandingan antara setiap query dan jangka dokumen. Menjelang akhir ini, kami tetapkan untuk setiap istilah dalam dokumen yang berat untuk istilah, yang tergantung pada jumlah kemunculan istilah dalam dokumen.
Dokumen Inverse Frekuensi
Istilah mentah frekuensi seperti di atas menderita masalah yang kritis: semua persyaratan yang
dianggap sama pentingnya ketika datang untuk menilai relevansi pada permintaan. Bahkan istilah tertentu memiliki sedikit atau tidak ada diskriminasi dalam menentukan kekuatan
relevansi.
Sebaliknya, adalah lebih umum digunakan untuk tujuan ini dokumen frekuensi quency DFT, didefinisikan sebagai jumlah dokumen dalam koleksi yang berisi istilah t. Hal ini karena dalam usaha untuk membedakan antara dokumen untuk tujuan penilaian lebih baik menggunakan tingkat dokumen statistik (seperti sebagai jumlah dokumen yang berisi istilah) daripada menggunakan koleksi-lebar statistik untuk istilah. Secara khusus, nilai cf baik mencoba dan asuransi yang kurang lebih sama, tetapi nilai-nilai df mereka berbeda secara signifikan.
Model ruang vektor untuk penilaian
Dalam Bagian ini kami mengembangkan pengertian tentang vektor dokumen yang menangkap kepentingan relatif dari istilah dalam dokumen. Representasi dari serangkaian dokumen sebagai vektor dalam ruang vektor yang umum dikenal sebagai space model vektor dan merupakan dasar informasi host operasi pengambilan dari scoring berkisar pada permintaan dokumen, dokumen klasifikasi dan dokumen clustering. Pertama-tama kita mengembangkan ide-ide dasar yang mendasari vector ruang mencetak; sebuah langkah penting dalam perkembangan ini adalah pandangan pertanyaan sebagai vektor dalam ruang vektor yang sama sebagai koleksi dokumen.
Titik Produk
Himpunan dokumen dalam koleksi kemudian dapat dipandang sebagai satu set vektor dalam sebuah ruang vektor, di mana terdapat satu sumbu untuk setiap istilah.
Bagaimana kita mengukur kesamaan antara dua dokumen dalam vector ruang? Upaya pertama mungkin mempertimbangkan besarnya perbedaan vector antara dua vektor dokumen. Ukuran ini menderita kekurangan: dua dokumen dengan isi yang sangat mirip dapat memiliki perbedaan yang signifikan vector hanya karena satu jauh lebih lama daripada yang lain. Jadi distribusi relative istilah mungkin identik dalam dua dokumen, tetapi istilah absolute frekuensi satu mungkin jauh lebih besar. Untuk mengimbangi efek dokumen panjang, cara standar
mengukur kesamaan antara dua dokumen (d1) dan d2 adalah untuk menghitung
kosinus kesamaan vektor mereka representasi ~ V (d1) dan ~ V kosinus kesamaan (d2) rumus (6.10)
Di mana pembilang mewakili perkalian titik dari vektor ~ V (d1) dan ~ V (d2), sedangkan penyebutnya adalah produk Euklidean lengths. Perkalian titik ~ x • Euclidean LENGTH ~ y dari dua vektor didefinisikan sebagai AM i = 1 Xiyi. Biarkan ~ V (d) menyatakan vektor dokumen untuk d, dengan M komponen ~ V 1 (d). . . ~ VM (d). The Euclidean panjang d didefinisikan sebagai q i = 1 ~ V 2 i (d). Efek dari penyebut Persamaan (6.10) dengan demikian untuk panjang-menormalkan. Normalisasi vektor ~ V ((d1)) dan ~ V (d2) ke unit vektor ~ v ((d1)) = ~ V ((d1)) / | ~ V ((d1)) |.
Komputasi nilai vector
Dalam pengaturan khas kami memiliki koleksi dokumen masing-masing diwakili oleh seorang
vektor, teks bebas query diwakili oleh vektor, dan bilangan bulat positif K. Kami mencari koleksi dokumen-dokumen K dengan skor tertinggi ruang vektor query yang diberikan. Kita sekarang memulai studi penentuan dokumen K dengan ruang vektor skor tertinggi untuk query tertentu. Biasanya, kita mencari ini K atas dokumen dalam diperintahkan oleh penurunan nilai; misalnya banyak pencarian mesin menggunakan K = 10 untuk mengambil dan peringkat-urutan halaman pertama sepuluh hasil terbaik. Di sini kami memberikan algoritma dasar perhitungan ini, kami mengembangkan perawatan lebih lengkap teknik dan pendekatan yang efisien.
COSINESCORE (q)
1 float Skor [N] = 0
2 Initialize Panjang [N]
3 untuk setiap query t jangka
4 lakukan menghitung wt, q dan mengambil daftar posting untuk t
5 untuk setiap pasangan (d, tft, d) dalam daftar posting
6 lakukan Skor [d] + = wft, d × wt, q
7 Baca array Length [d]
8 untuk masing-masing d
9 melakukan Skor [d] = Skor [d] / Length [d]
10 kembali ke K komponen Top Skor []
Gambar 6.14 ◮ algoritma dasar untuk menghitung skor ruang vektor.
Gambar 6.14 memberikan algoritma dasar untuk menghitung skor ruang vektor. Panjang array memegang panjang (faktor normalisasi) untuk masing-masing dari N dokumen, sedangkan memegang Skor array nilai untuk masing-masing dokumen. Ketika skor akhirnya dihitung pada Langkah 9, semua itu tetap dalam Langkah 10 adalah untuk memilih dari dokumen K dengan skor tertinggi.
Diposting oleh
Zaoldyek Hunter Modunk
Label:
sistem temu balik informasi
Sabtu, 24 April 2010
di
21.51
|
tugas individu STBI part2
Resume
buku Christopher D. Manning, Prabhakar Raghavan, Hinrich Schütze teks 4 dan teks 6
Konstruksi Index
Dalam bab ini, kita melihat bagaimana membangun sebuah indeks terbalik. Kami akan memanggil proses konstruksi indeks atau pengindeksan dan proses atau mesin yang melaksanakan pengindeksan. Rancangan algoritma pengindeksan diatur oleh batasan hardware. Oleh karena itu kita akan memulai bab ini dengan tinjauan dasar-dasar perangkat keras komputer yang relevan untuk pengindeksan. Kami kemudian memperkenalkan semacam berbasis pengindeksan yang diblokir, sebuah mesin tunggal algoritma yang efisien yang dirancang untuk statis koleksi yang dapat dilihat sebagai yang lebih scalable. Untuk koleksi yang sangat besar seperti web, pengindeksan harus didistribusikan melalui kelompok komputer dengan ratusan atau ribuan mesin. Akhirnya, kita akan membahas beberapa komplikasi yang dapat timbul dalam pengindeksan. Seperti keamanan dan indeks untuk pengambilan peringkat. Dalam pencarian web, dokumen tidak pada sistem file lokal, tapi harus spider atau merangkak. Di pencarian perusahaan, sebagian besar dokumen yang terangkum dalam manajemen konten bervariasi sistem, aplikasi email dan database. Sementara sebagian besar aplikasi ini dapat diakses melalui http, API biasanya lebih efisien. Pembaca harus menyadari bahwa bangunan sub-sistem yang berupa teks mentah untuk proses pengindeksan dapat dengan sendirinya menjadi masalah yang menantang.
Dasar Hardware
Banyak keputusan ketika membangun sebuah sistem pencarian informasi yang didasarkan pada karakteristik dari sistem perangkat keras komputer. Karena itu kita memulai bab ini dengan tinjauan singkat perangkat keras komputer. Sebuah dasar daftar hardware yang akan kita butuhkan dalam pembahasan ini untuk memotivasi sistem IR desain berikut.
• Akses ke data dalam memori jauh lebih cepat daripada akses data pada disk. Ini mengambil beberapa clock cycle (mungkin 5 × 10-9 detik) untuk mengakses byte memori, tetapi lebih lama untuk transfer dari disk (sekitar 2 × 10-8 detik). Akibatnya, kita ingin menyimpan data sebanyak mungkin dalam memori, terutama data yang sering kita butuhkan untuk mengakses. Kita sebut teknik yang sering digunakan menyimpan data disk caching dalam cache memori utama.
• Ketika melakukan sebuah disk membaca atau menulis, butuh beberapa saat untuk disk head untuk pindah ke bagian disk tempat data berada. Kali ini disebut mencari waktu dan ini adalah tentang 5ms pada umumnya rata-rata untuk disk. Tidak ada data sedang ditransfer selama mencari. Dalam rangka untuk memaksimalkan transfer data bunga, potongan data yang akan dibaca harus disimpan pada disk. Sebagai contoh, menggunakan angka-angka pada Tabel 4.1 hal itu mungkin memakan waktu sedikitnya 0,2 detik untuk mentransfer 10 MB dari disk ke memori jika disimpan sebagai salah satu bongkahan, tetapi sampai 0.2 + 100 × (5 × 10-3) = 0,7 detik jika disimpan dalam 100 non-contiguous bongkahan karena kita perlu memindahkan disk kepala sampai dengan 100 kali.
• Sistem operasi umumnya membaca dan menulis seluruh blok. Dengan demikian, membaca
satu byte dari disk dapat mengambil waktu sebanyak membaca seluruh blok. Ukuran blok dari 8 KB, 16 KB, 32 KB dan 64 KB yang umum.
• Data transfer dari disk ke memory akan ditangani oleh systembus, bukan oleh prosesor. Ini berarti bahwa prosesor yang tersedia untuk memproses data saat disk I / O. Kita dapat memanfaatkan fakta ini untuk mempercepat transfer data dengan dikompresi menyimpan data pada disk. Dengan asumsi yang efisien dekompresi algoritma, total waktu membaca dan kemudia dikompresi data biasanya kurang daripada membaca data yang tidak dikompresi.
• Server yang digunakan dalam sistem IR biasanya memiliki beberapa GB memori utama, kadang-kadang puluhan GB. Ruang disk yang tersedia adalah beberapa kali lipat lebih besar.
Blocked sort-based indexing
Pertama-tama membuat perakitan koleksi semua docID istilah-pasangan. Kemudian menyortir pasangan dengan istilah sebagai kunci dominan dan docID sebagai kunci sekunder. Akhirnya, kami mengatur untuk setiap docIDs istilah ke daftar posting dan menghitung statistik seperti frekuensi term dan dokumen. Untuk koleksi yang kecil, semua ini dapat dilakukan di memori. Kami akan menjelaskan metode untuk koleksi besar yang memerlukan penggunaan sekunder penyimpanan. Untuk membuat pembangunan index lebih efisien, kami mewakili istilah termIDs, di mana masing-masing adalah unik termID nomor seri. Kita dapat membangun pemetaan dari istilah ke termIDs on the fly sementara kami memproses koleksi, dalam dua pendekatan lulus, kami menyusun kosakata pertama dan membangun indeks terbalik. Algoritma konstruksi indeks yang dijelaskan dalam bab ini melewati satu data. Jika ukuran file antara selama indeks konstruksi dalam faktor kecil memori yang tersedia, maka teknik kompresi dapat membantu; tetapi banyak koleksi file posting yang besar tidak bisa masuk ke dalam memori bahkan setelah kompresi. Dengan memori utama tidak mencukupi, kita perlu menggunakan algoritma sorting eksternal. Untuk dapat diterima kecepatan, persyaratan pusat algoritma semacam itu adalah bahwa hal itu meminimalkan jumlah random disk yang mencari selama sequential pemilahan disk dibaca jauh lebih cepat daripada mencari seperti yang kita jelaskan sebelumnya. Salah satu solusinya adalah blocked sort-berbasis algoritma pengindeksan atau BSBI pada Gambar 4.2. BSBI (i) segmen koleksi menjadi beberapa bagian dengan ukuran yang sama, (ii) memilah termID pasang docID setiap bagian dalam memori, (iii) toko intermediate diurutkan hasilnya pada disk dan (iv) gabungan semua hasil menengah ke dalam akhir indeks.
Algoritma memparsing dokumen ke termID-docID dan mengakumulasi pasangan
pasangan dalam memory sampai blok ukuran tetap penuh pada Gambar 4.2. Kami memilih ukuran blok untuk menyesuaikan dengan nyaman ke dalam memori untuk
izin yang cepat dalam-memori semacam itu. Blok ini kemudian dibalik dan ditulis ke disk.
Inversi melibatkan dua langkah. Pertama kita menyortir pasangan termID-inversi docID. Berikutnya kami kumpulkan semua termID-docID berpasangan dengan termID yang sama ke dalam daftar posting, dimana posting hanyalah sebuah docID. Hasilnya, indeks terbalik untuk blok baru saja kita baca, kemudian ditulis ke disk.
Single-pass di memori pengindeksan
Blocked sort berbasis skala pengindeksan memiliki sifat yang sangat baik. Untuk koleksi yang sangat besar, struktur data ini tidak muat ke dalam memori. Alternatif yang lebih scalable adalah
single-pass di memori atau SPIMI pengindeksan. SPIMI dapat mengindeks koleksi dari berbagai ukuran asalkan ada cukupruang disk yang tersedia. SPIMI-invert disebut berulang pada token sungai sampai seluruh koleksi telah diproses. Token diproses satu per satu. Ketika sebuah istilah terjadi untuk pertama kali, itu akan ditambahkan ke kamus, dan daftar posting baru diciptakan. Perbedaan antara BSBI dan SPIMI adalah bahwa SPIMI menambahkan posting langsung
ke daftar posting. Daripada pertama mengumpulkan semua pasangan termID-docID
kemudian menyortir mereka (seperti yang kita lakukan di BSBI), masing-masing daftar posting adalah dinamis dan akan segera tersedia untuk mengumpulkan posting. Ini memiliki dua keuntungan. Hal ini akan menghemat memori karena kita melacak istilah milik sebuah daftar posting, sehingga termIDs dari posting tidak perlu disimpan. Sebagai hasilnya, indeks proses pembangunan secara keseluruhan lebih efisien.
Distributed pengindeksan
Koleksi sering begitu besar sehingga kita tidak dapat melakukan konstruksi indeks yang efisien
pada satu mesin. Hal ini terutama berlaku dari World Wide Web dimana kita membutuhkan komputer yang besar untuk membangun apapun. Oleh karena itu mesin pencari web didistribusikan menggunakan algoritma pengindeksan untuk indeks konstruksi. Hasil dari proses pembangunan adalah indeks yang didistribusikan terbagi di beberapa mesin, baik menurut istilah atau sesuai dengan dokumen. Inti dari sebuah cluster adalah memecahkan masalah komputasi besar komoditas murah mesin atau node yang dibangun dari standar bagian (prosesor, memori, disk) sebagai lawan pada sebuah super komputer dengan perangkat keras khusus. Sementara ratusan atau ribuan dari mesin tersedia dalam kelompok-kelompok seperti itu, mesin bisa gagal setiap waktu. Satu persyaratan untuk mengindeks terdistribusi kuat karena itu yang kita
membagi pekerjaan ke dalam potongan-potongan yang kita dapat dengan mudah menetapkan dan - dalam kasus failure - menugaskan kembali.
Pengindeksan dynamic
Istilah-istilah baru perlu ditambahkan ke dalam kamus, dan daftar posting perlu diperbarui untuk istilah-istilah yang ada. Cara paling mudah untuk mencapai ini adalah dengan merekonstruksi secara berkala indeks dari nol. Ini adalah solusi yang baik jika sejumlah perubahan dari waktu ke waktu adalahkecil dan penundaan dalam membuat dokumen baru dicari dapat diterima, dan
jika cukup banyak sumber daya yang tersedia untuk membangun indeks baru sementara yang lama masih tersedia untuk query. Sebuah indeks dan largemain indeks tambahan kecil
yang menyimpan dokumen baru. Indeks auxiliary disimpan di dalam memori. Pencarian
dijalankan di kedua indeks dan hasil penggabungan. Penghapusan disimpan dalam sebuah penghapusan bit vektor. Kita dapat menyaring dokumen dihapus sebelum kembali
hasil pencarian. Dokumen diperbarui dengan menghapus dan memasukkan kembali dokumen tersebut.
.
Jenis indeks
Algoritma yang dibahas di sini semua bisa diterapkan untuk posisi indeks. Dalam indeks kita telah mempertimbangkan sejauh ini, daftar posting diperintahkan dengan terhadap docID. Hal ini menguntungkan untuk kompresi - docIDs bukannya lebih kecil kita dapat menekan kesenjangan antara ID, sehingga mengurangi kebutuhan ruang untuk indeks. Namun, struktur ini
untuk indeks tidak optimal ketika kita membangun peringkat peringkat Retrieval, dibandingkan dengan sistem pengambilan Boolean. Dalam peringkat pencarian, posting sering disusun berdasarkan berat badan atau dampak, dengan bobot tertinggi posting pertama terjadi. Dengan susunan ini, scanning postingan daftar selama pemrosesan query biasanya dapat dihentikan lebih awal ketika beban telah menjadi begitu kecil sehingga dokumen lebih lanjut dapat diperkirakan dari rendah kesamaan dengan query.
Skor, Istilah Bobot dan Model Ruang Vector
Sejauh ini kita telah berurusan dengan indeks yang mendukung Boolean queries. Dalam kasus koleksi dokumen besar, jumlah hasil dokumen yang sesuai dapat jauh melebihi jumlah pengguna manusia yang bisa menyaring. Oleh karena itu, penting untuk sebuah mesin pencari untuk menentukan peringkat-memesan pencocokan dokumen permintaan. Bab ini terdiri dari tiga ide pokok :
1. Kami memperkenalkan parametrik dan zona indeks, yang berfungsi
dua tujuan. Pertama, mereka memungkinkan kita untuk mengindeks dan mengambil dokumen oleh metadata seperti bahasa di mana sebuah dokumen yang tertulis. Kedua,
mereka memberi kita sarana untuk penilaian sederhana (dan dengan demikian peringkat) dokumen sebagai tanggapan atas permintaan.
2. Selanjutnya, kita mengembangkan gagasan bobot pentingnya istilah dalam dokumen, berdasarkan statistik terjadinya istilah.
3. Setelah itu kami menunjukkan bahwa dengan melihat setiap dokumen sebagai vektor seperti berat, kita dapat menghitung skor antara permintaan dan setiap dokumen.
Pandangan ini dikenal sebagai ruang vektor mencetak gol.
Parametric dan zona indeks
Sebagian besar dokumen memiliki struktur tambahan. Umumnya dokumen digital menyandi,
mesin dikenali dalam bentuk, metadata tertentu yang terkait MET dengan setiap dokumen.
Dengan metadata, kita berarti bentuk-bentuk khusus data tentang dokumen, seperti
sebagai penulis (s), judul dan tanggal publikasi. Metadata ini akan umumnya meliputi bidang-bidang seperti tanggal penciptaan dan format dokumen, baik penulis dan mungkin judul dokumen.
Pertimbangkan pertanyaan dari form "menemukan dokumen yang ditulis oleh WilliamShakespeare pada tahun 1601, yang berisi frase sayangnya Yorick miskin ". Pemrosesan query kemudian seperti biasa terdiri dari posting persimpangan, kecuali bahwa kita dapat menggabungkan posting dari standar terbalik serta indeks parametrik. Ada satu parametric indeks untuk masing-masing bidang; hal itu memungkinkan kita untuk memilih hanya
pencocokan dokumen tanggal yang ditentukan dalam pencarian.
Zona mirip dengan bidang, kecuali isi zona dapat berupa teks bebas. Sedangkan lapangan mungkin diperlukan waktu yang relatif kecil pada seperangkat nilai, zona dapat dianggap sebagai sewenang-wenang, jumlah teks terbatas. Misalnya, judul dan abstrak dokumen umumnya diperlakukan sebagai zona. Kita mungkin membangun sebuah indeks terbalik terpisah untuk setiap zona dari sebuah dokumen, untuk mendukung permintaan tersebut sebagai "menemukan dokumen dengan pedagang di judul dan william dalam daftar penulis dan ungkapan hujan lembut di dalam tubuh ". Hal ini memiliki efek membangun indeks. Sedangkan dalam kamus untuk indeks parametric berasal dari kosakata yang tetap (himpunan bahasa, atau set tanggal), yang kamus untuk indeks zona struktur harus kosa kata apa pun yang berasal dari
teks zona itu.
Berat zona scoring
Kita telah berfokus pada pengambilan dokumen berdasarkan Boolean query di ladang dan zona. Kita sekarang beralih ke aplikasi kedua zona dan ladang. Boolean query diberi q dan sebuah dokumen d zona tertimbang menetapkan skor ke pasangan (q, d) suatu nilai dalam interval [0, 1], dengan menghitung kombinasi linear zona nilai, di mana setiap zona dokumen menyumbangkan Boolean nilai. Lebih khusus lagi, pertimbangkan satu set dokumen masing-masing memiliki ℓ
zona. Biarkan g1,. . . , G ℓ ∈ [0, 1] sehingga ℓ å i = 1 gi = 1. Untuk 1 ≤ i ≤ ℓ, biarkan si menjadi
Nilai boolean yang menunjukkan pertandingan (atau ketiadaan daripadanya) antara q dan engan
zona. Misalnya, nilai Boolean dari zona bisa 1 jika semua permintaan istilah (s) yang terjadi di zona itu, dan nol sebaliknya; memang, itu bisa setiap Boolean fungsi yang memetakan kehadiran istilah permintaan dalam zona ke 0, 1. Kemudian, zona skor tertimbang didefinisikan sebagai
ZONESCORE (Q1, q2)
1 float nilai [N] = [0]
2 konstan g [ℓ]
3 p1 ← postingan lama (Q1)
4 p2 ← postingan lama (q2)
5 / / nilai [] adalah sebuah array dengan skor entri untuk setiap dokumen, diinisialisasi ke nol.
6 / / p1 dan p2 adalah diinisialisasi agar menunjuk ke awal masing-masing posting.
7 / / Asumsikan g [] adalah untuk melakukan masing-masing zona bobot.
8 sementara p1 6 = NIL dan p2 6 = NIL
9 lakukan jika docID (p1) = docID (p2)
10 maka skor [docID (p1)] ← WEIGHTEDZONE (p1, p2, g)
11 p1 ← berikutnya (p1)
12 p2 ← berikutnya (p2)
13 else if docID (p1) Belajar beban
Bagaimana kita menentukan bobot tertimbang gi untuk zona scoring? Bobot ini dapat ditentukan oleh seorang ahli (atau, pada prinsipnya, user); namun semakin, bobot ini adalah "belajar" dengan menggunakan contoh-contoh pelatihan yang telah dinilai editorial. Metodologi yang terakhir ini berada di bawah kelas umum pendekatan untuk penilaian dan peringkat dalam pencarian informasi, yang dikenal sebagai mesin-belajar relevansi. Kami menyediakan pengenalan singkat dengan topik ini di sini karena zona tertimbang mencetak menyajikan pengaturan yang bersih untuk memperkenalkan itu; sebuah lengkap tuntutan perkembangan pemahaman pembelajaran mesin.
Sejauh ini, skor telah bergantung pada apakah atau tidak istilah query hadir dalam
zona dalam dokumen. Kami mengambil langkah logis berikutnya: sebuah dokumen atau
zona yang menyebutkan istilah query lebih sering lebih berkaitan dengan permintaan
dan karenanya harus menerima skor yang lebih tinggi. Untuk memotivasi ini, kita mengingat
pengertian tentang permintaan teks bebas diperkenalkan sebelumnya: query di mana
persyaratan query diketik ke dalam bentuk yang unik antarmuka pencarian, tanpa
menghubungkan operator pencarian (seperti Boolean operator). Query ini gaya, yang sangat populer di Web, pandangan query hanya sebagai kumpulan kata-kata. Sebuah mekanisme penilaian yang masuk akal maka adalah untuk menghitung skor. Singkatnya, di atas istilah permintaan, skor pertandingan antara setiap query dan jangka dokumen. Menjelang akhir ini, kami tetapkan untuk setiap istilah dalam dokumen yang berat untuk istilah, yang tergantung pada jumlah kemunculan istilah dalam dokumen.
Dokumen Inverse Frekuensi
Istilah mentah frekuensi seperti di atas menderita masalah yang kritis: semua persyaratan yang
dianggap sama pentingnya ketika datang untuk menilai relevansi pada permintaan. Bahkan istilah tertentu memiliki sedikit atau tidak ada diskriminasi dalam menentukan kekuatan
relevansi.
Sebaliknya, adalah lebih umum digunakan untuk tujuan ini dokumen frekuensi quency DFT, didefinisikan sebagai jumlah dokumen dalam koleksi yang berisi istilah t. Hal ini karena dalam usaha untuk membedakan antara dokumen untuk tujuan penilaian lebih baik menggunakan tingkat dokumen statistik (seperti sebagai jumlah dokumen yang berisi istilah) daripada menggunakan koleksi-lebar statistik untuk istilah. Secara khusus, nilai cf baik mencoba dan asuransi yang kurang lebih sama, tetapi nilai-nilai df mereka berbeda secara signifikan.
Model ruang vektor untuk penilaian
Dalam Bagian ini kami mengembangkan pengertian tentang vektor dokumen yang menangkap kepentingan relatif dari istilah dalam dokumen. Representasi dari serangkaian dokumen sebagai vektor dalam ruang vektor yang umum dikenal sebagai space model vektor dan merupakan dasar informasi host operasi pengambilan dari scoring berkisar pada permintaan dokumen, dokumen klasifikasi dan dokumen clustering. Pertama-tama kita mengembangkan ide-ide dasar yang mendasari vector ruang mencetak; sebuah langkah penting dalam perkembangan ini adalah pandangan pertanyaan sebagai vektor dalam ruang vektor yang sama sebagai koleksi dokumen.
Titik Produk
Himpunan dokumen dalam koleksi kemudian dapat dipandang sebagai satu set vektor dalam sebuah ruang vektor, di mana terdapat satu sumbu untuk setiap istilah.
Bagaimana kita mengukur kesamaan antara dua dokumen dalam vector ruang? Upaya pertama mungkin mempertimbangkan besarnya perbedaan vector antara dua vektor dokumen. Ukuran ini menderita kekurangan: dua dokumen dengan isi yang sangat mirip dapat memiliki perbedaan yang signifikan vector hanya karena satu jauh lebih lama daripada yang lain. Jadi distribusi relative istilah mungkin identik dalam dua dokumen, tetapi istilah absolute frekuensi satu mungkin jauh lebih besar. Untuk mengimbangi efek dokumen panjang, cara standar
mengukur kesamaan antara dua dokumen (d1) dan d2 adalah untuk menghitung
kosinus kesamaan vektor mereka representasi ~ V (d1) dan ~ V kosinus kesamaan (d2) rumus (6.10)
Di mana pembilang mewakili perkalian titik dari vektor ~ V (d1) dan ~ V (d2), sedangkan penyebutnya adalah produk Euklidean lengths. Perkalian titik ~ x • Euclidean LENGTH ~ y dari dua vektor didefinisikan sebagai AM i = 1 Xiyi. Biarkan ~ V (d) menyatakan vektor dokumen untuk d, dengan M komponen ~ V 1 (d). . . ~ VM (d). The Euclidean panjang d didefinisikan sebagai q i = 1 ~ V 2 i (d). Efek dari penyebut Persamaan (6.10) dengan demikian untuk panjang-menormalkan. Normalisasi vektor ~ V ((d1)) dan ~ V (d2) ke unit vektor ~ v ((d1)) = ~ V ((d1)) / | ~ V ((d1)) |.
Komputasi nilai vector
Dalam pengaturan khas kami memiliki koleksi dokumen masing-masing diwakili oleh seorang
vektor, teks bebas query diwakili oleh vektor, dan bilangan bulat positif K. Kami mencari koleksi dokumen-dokumen K dengan skor tertinggi ruang vektor query yang diberikan. Kita sekarang memulai studi penentuan dokumen K dengan ruang vektor skor tertinggi untuk query tertentu. Biasanya, kita mencari ini K atas dokumen dalam diperintahkan oleh penurunan nilai; misalnya banyak pencarian mesin menggunakan K = 10 untuk mengambil dan peringkat-urutan halaman pertama sepuluh hasil terbaik. Di sini kami memberikan algoritma dasar perhitungan ini, kami mengembangkan perawatan lebih lengkap teknik dan pendekatan yang efisien.
COSINESCORE (q)
1 float Skor [N] = 0
2 Initialize Panjang [N]
3 untuk setiap query t jangka
4 lakukan menghitung wt, q dan mengambil daftar posting untuk t
5 untuk setiap pasangan (d, tft, d) dalam daftar posting
6 lakukan Skor [d] + = wft, d × wt, q
7 Baca array Length [d]
8 untuk masing-masing d
9 melakukan Skor [d] = Skor [d] / Length [d]
10 kembali ke K komponen Top Skor []
Gambar 6.14 ◮ algoritma dasar untuk menghitung skor ruang vektor.
Gambar 6.14 memberikan algoritma dasar untuk menghitung skor ruang vektor. Panjang array memegang panjang (faktor normalisasi) untuk masing-masing dari N dokumen, sedangkan memegang Skor array nilai untuk masing-masing dokumen. Ketika skor akhirnya dihitung pada Langkah 9, semua itu tetap dalam Langkah 10 adalah untuk memilih dari dokumen K dengan skor tertinggi.
Diposting oleh
Zaoldyek Hunter Modunk
Label:
sistem temu balik informasi
|
MARVEL and SPIDER-MAN: TM & 2007 Marvel Characters, Inc. Motion Picture © 2007 Columbia Pictures Industries, Inc. All Rights Reserved. 2007 Sony Pictures Digital Inc. All rights reserved. blogger templates |
