EdyWinarno.Com

|Computer|Blogging|Programming|Informatics|Network|Technology|

Teknik Pengalamatan dalam Algoritma dan Pemrograman

Comments Off
Posted by edy winarno on March 12, 2010 at 8:53 am

Teknik  Pengalamatan

Rekaman- rekaman dalam suatu berkas nalari diciri (diidentifikasi) oleh perangkat nomer yang unik atau kelompok karakter yang unik.

Perangkat ini disebut kunci, biasanya menempati medan yang panjangnya tetap dalam masing- masing rekaman. Untuk membentuk suatu kunci yang unik kadang- kadang diperlukan gabungan dua medan atau lebih yang disebut kunci berderet. (concatenated key)

Dalam beberapa berkas, rekaman- rekaman berisi lebih dari satu kunci. Misalnya barang yang sudah dibeli mempunyai nomer penyalur dan nomer pemakai yang berbeda. Keduanya dipakai sebagai kunci. Kunci harus unik, karena kunci itu dipakai untuk menentukan di mana rekaman harus diambil dari unit  berkas dan untukk melacak rekaman itu dari berkasnya. Ini disebut kunci utama atau penciri (identifier).

Persoalan dari pengalamatan berkas adalah: diberikan kunci utama, lalu bagaiman komputer mengambil rekaman atau kunci itu? Ada berbagai teknik pengalamatan rekaman.

Teknik 1 : Pemayaran Berkas (Scanning the file)

Cara yang paling sederhana untuk pengambilan rekaman adlah memayar berkas dengan memeriksa kunci setiap rekaman. Metode ini sangat lambat dan hanya mungkin digunakan dalam operasi pemrosesan kelompok yang memakai berkas serial, seperti pita, di mana setiap rekaman mau tidak mau harus dibaca.

Teknik 2 : Pencarian Ruas (Block Search)

Pada rekaman- rekaman yang diorganisasikan serial dengan kunci, tidak perlu setiap rekaman dibaca pada waktu memayar berkas.

Berkas itu dalam urutan kunci utama yang menanjak (ascending). Misalnya kunci rekaman yang dicari Ks, maka pencarian dimulai dari kunci- kunci ruas yang kecil. Seperti halnya pembagian rentetan pada bab sebelumnya, ukuran ruas yang optimum adalah NB = . Nf adalah jumlah rekaman daklam berkas. Pada pemeriksaan kalau ditemukan rekaman yang kuncinya pertama kalau kali lebih besar dari Ks, maka rekaman- rekaman dari ruas yang baru saja diloncati diperiksa (dipayar) sampai ditemukan rekaman dengan kunci Ks.Kadang- kadang cara ini disebut pencarian loncatan (skiipsearch). Misalnya ada 10.000 rekaman dalam suatu berkas. Ruas pencarian terdiri atas 100 rekaman. Rata-rata ada 100 rekaman yang diperiksa sehingga ditemukan rekaman yang diminta. Proses pencarian baru akan dilakukan pada ruas yang mengandung rekaman yang diminta. Dalam praktek tidak ada pencarian ruas yang rekamannya sampai 10.000, yang berarti seluruh berkas ada 10.0002 rekaman . Dalam hal ini diperlukan index yang mewakili seluruh rekaman. Kemudian pada index inilah dilakukan pembagian ruas-ruas pencarian.

Teknik  3. Pencarian Biner ( Binary Search )

Pencarian biner pertama-tama menuju ketengah-tengah area yang mengandung rekaman yang diminta. Lalu membandingkan kunci rekaman yang ditengah-tengah itu dengan kunci yang dicari. Maka akan diketahui bahwa kunci yang dicari letaknya dibelahan yang mana. Kemudian menuju ketengah-tengah belahan itu lagi .Proses ini diulangi terus menerus. Berkas diperiksa rata-rata kurang lebih       (log 2 Nf -1 ) kali. Untuk harga Nf (jumlah rekaman dalam berkas) yang besar, log Nf – 1 lebih kecil daipada   .

Pencarian biner umumnya tidak tepat untuk pencarian pada piranti simpanan masup langsung, karena menghabiskan banyak waktu. Pencarian biner tidak dapat dipakai untuk pencarian pada rentetan, karena komputer tidak mempunyai peralatan untuk mengatur pencarian itu.  Sepaerti diketahui rentetan terdiri atas rekaman-rekaman yang disatukan dengan pointer, sehingga sulit untuk menentukan titik tengahnya. Pencarian biner bermanfaat untuk pencarian rinci-rinci dalam memori utama atau simpanan tingkat padat (misalnya hard disk ).

Jenis khusus dari pencarian biner adalah rinci-rinci yang dicari tidak disusun berurutan, tetapi dalam bentuk pohon biner dengan pointer-pointer. Kemudian pencarian diteruskan dengan menelusuri pointer-pointer. Keuntungan bentuk pencarian ini adalah bahwa rekaman – rekaman baru dapat disisipkan ke dalam berkas , tanpa harus menggeser ke samping ( proses ini merupakan operasi yang janggal dan memakan waktu). Titik tengah yang dituju akan bergeser untuk menyesuaikan penambahan itu.

Pencarian biner lebih baik dilakukan pada index-index berkas daripada langsung mencari berkasnya sendiri.

Teknik 4 . Berkas Serial Berindex

Pada umumnya pemayaran atau pencarian berkas-berkas untuk mendapatkan suatu rinci terlalu banyak memakan waktu. Metode tersebut hanya dipakai untuk menudingsuatu rinci dalam area yang kecil setelah teknik-teknik yang lain menemukan area yang ditempatinya.

Pemayaran cakram atau alur drum dapat dibuat bersamaan dengan waktu rotasi dan karena itu bermanfaat.

Apabila berkas mempunyai kunci yang berurutan, biasanya digunakan tabel yang disebut index . Masukan pada tabel adalah kunci rekaman yang dicari, danhasil operasi pencarian tabel adalah alamat relatif atau alamat sesungguhnya dari rekaman itu pada unit berkas.

Suatu index didefinisikan sebagai suatu tabel di mana beroperasi dengan prosedur yang menerima informasi tentang harga-harga atribet tertentu sebagai masukan, dan sebagai keluaran memberikan informasiyang membantu pengambilan rekaman dengan cepat, di mana rekaman itulah yang memiliki harga-harga atribut tersebut. Index utama adalah index yang menggunakan ciri rekaman (kunci utama) sebagai masukan dan memberikan informasi tentang lokasi fisis dari rekaman sebagai keluara. Index sekunder adalah index yangmengunakan kunci yang tidak unik, tapi dapat mewakili sejumlah rekaman.

Index kadang- kadang disebut sebagai penuntun (directory) yang memberikan informasi tentang pertalianantara rekaman- rekaman, sebagai contoh, memberikan hubungan- hubungan dalam struktur jaring atau stuktur pohon.

Apabila suatu index dipakai untuk pengelamatan berkas, maka komputer harus mencari index, bukan mencari berkas itu. Cara ini dapat menghemat banyak sekali waktu, tetapi dibuthkan ruangan untuk menyimpan index itu. Hal ini mirip dengan penggunaan indek kartu dalam perpustakaan. Pemakai mencari nama buku yang dia perludi dalam index kartu, dan index kartu itu memberikan nomor katalog, yang analog dengan alamat relatifdari letak buku itu pada ra

Apabila berkas mempunyai kunci yang berurutan, umumnya index tidak berisi acuan untuk setiap rekaman, tetapi cukup satuan acuan untuk ruas- ruas rekaman.

Pengacuan ruas- ruas rekaman dibandingkan dengan pengacuan pada rekaman individu sangant banyak mengurangi ukuran indek. Walaupun demikian index seringkali terlalu besar untuk dicari dalam keseluruhannya, dan dengan demikian diperlukan suatu index untuk sejumlah index.

Untuk menghemat waktu pencarian, segmen- segmen dari iondex tingkat lebih rendah dapat diedarkan di antara rekaman- rekaman data yang bersangkutan

Pada area berkas yang diwakili satu index, dilakukan pencarian dengan metode pencarian ruas atau pencarian biner maupun pemayaran. Pada berkas cakram biasanya mempunyai satu alur index untuk setiap silinder, yang berisi acuan – acuan untuk rekaman- rekaman yang tersimpan dalam silinder itu.

Berkas serial berindex merupakan bentuk yang paling umum dari pengalamatan berkas. Mode lokasi VIA dari CODASYL memakai teknik ini.

Teknik 5 : Berkas Tak Berurutan Berindex (Indexed Nonsequential Files)

Berkas yang tak berurutan dapat diberi index seperti halnya berkas berurutan. Tetapi memerlukan index yang jauh lebih banyak, karena harus berisi satu entry untuk satu rekaman. Lagi pula, harus berisi alamat lengkap tertentu (atau alamat relatip), sedangkan suatu index pada berkas berurutan dapat memotong alamat yang dikandungnya, karena urutan karakter tingkat tinggidari alamat berturut-turut biasanya sama.

Misalnya APNA, APNE, APNI, APNK, dan seterusnya. Dalam hal ini APN sama semua.

Berkas berurutan berindex jauh lebih ekonomis, karena ruang index jauh lebih sedikit dan waktu pencarian lebih cepat.

Alasan utama tetap digunakanya berkas tak berurutan ialah bahwa harus dialamatkan lebih dari satu kunci. Apabila kunci yang satu diurutkan, maka kunci yang lain tidak akan terurutkan. Suatu index dapat dipakai untuk tiap kunci, index untuk kunci berurutan mempunyai satu entry per ruas. Sedang kunci tak berurutan, satu entry untuk setiap rekaman. Untuk berkas yang berkunci banyak, kunci yang paling sering dipakai biasanya yang diurutkan, karena masup cepat dimungkinkan oleh index berurutan pendek.

Analogi index kartu perpustakaan lebih tepat untuk berkas berurutan berindex. Dua kunci dipakai dalam indek kartu, yakni judul buku dan nama pengarang. Kedua kunci ini tidak dipakai untuk pengurutan buku- buku pada rak- rak. Oleh karena itu harus ada suatu entri untuk setiap buku dalam kedua index it.

Buku- buku itu disusun dalam urutan dengan nomor katalog, Apabila pemakai telah menemukan nomor katalog dari buku yang diinginkannya, lalu dia mencari pada jajaran-jajaran rak (lemari- lemari rak). Analog dengan pencarian Index dalam berkas. Masing- masing jajaran rak biasanya terdapat tanda nomor permulaan dan nomor akhir katalog dari buku- buku dalam jajaran itu. Pemakai membandingkan nomor katalog yang telah diperoleh dengan batasan nomor pada jajaran itu. Apabila  nomor katalog yang dipegangnya berada dalam batasan itu, berarti buku yang dicari berada dalam jajaran itu. Lalu dicocokkan batasan nomor pada tiap rak dalam jajaran itu. Analog dengan index induk pada suatu index silinder dam kemudian pada index  alur. Setelah menemukan rak yang memuat buku tersebut , lalu pemakai mencari- cari buku tersebut dalam rak itu. Dalam hal ini pencarian dalam berkas dapat menggunakan metode pencarian ruas ataupun pemayaran dan pencarian biner.

Index perpustakaan tidak menunjukkan lokasi fisis dari buku pada raknya. Tetapi memberikan pada nomor katalog yang dapat dianggap sebagai alamat relatif atau alamat simbul. Alasannya dipakai alamat simbul ialah kalau alamat fisis yang dipakai, lalu karena buku-buku dalan rak selalu bergeser tempatnya, maka index perpustakaan harus sering diperbarui/ diubah. Dengan alasan yang sama berkas tak berurutan berindex juga kadang- kadang memakai simbul daripada alamat sungguh. Penambahan rekaman baru dan penghapusan rekaman lama selalu menggeser lokasi rekaman- rekaman.

Apabila lebih dari satu kunci digunakan dalan rekaman- rekaman. Index pada suatu kunci yang bukan utama dapat menunjukkan kunci utama dari rekaman sebagai keluarannya. Kunci utama ini kemudian digunakan untuk pengembilan rekaman dengan pengalamatan yang lain. Analogi dengan index perpustakaan, misalnya judul buku adalah kunci utama, sedang nama pengarangbukan kunci utama. Dengan kunci nama pengarang, kitadapat menemukan kunci utamanya. Metode dengan menggunakan alamat simbul lebih lambat daripada alamat fisis, tetapi pada berkas yang rekaman- rekamannya sering berubah posisinya, pengalamatan simbul menunjuk manfaatnya.

Alasan lain untuk penggunaan susunan rekaman tak berurutan adalah bahwa berkas itu sangaty lincah dan penyisipan penghapusan ke dalam berkas yang berurutan akan terlalu sulit dan terlalu makan waktu. Apabilabuku yang disimpan dalam rak diurutkan menurut abjadnya, maka pemeliharaannya memerlukan waktu banyak, karenasetiap kali ditambahkan buku baru, sejumlah buku harus digeser. Kalau buku- buku itu tak berurutan, tapitapi nomor katalognya berurutan, maka buku barudapat diletakkan pada posisi terakhir dengan nomor urut katalog yang terakhir.

Teknik 6 : Pengalamatan Alamat Setara Kunci

(Key- Equals- Address)

Berbagai metode pengubahan kunci langsung ke dalam suatu alamat berkas dipakai. Penggunaan metode- metode ini dapat menghasilkan perangkat pengalamatan yang tercepat dan tidak diperlukan pencarian berkasatau operasi index.

Cara pemecahan persoalan pengalamatan yang paling sederhana aialah dalam transaksi input, memiliki alamatsama dengan kunci supaya pengambilannya sederhana.Pola ini termasuk pengalamatan langsung.Dlam banyak aplikasi, pendekatan langsung ini tidak dimungkikan. Nomor- nomor barang dari suatu pabrik tidak dapat diubah untuk menyesuaikan komputer karena nomor- nomor itu mempunyai arti yang penting bagi perusahaan tersebut.

Kadang- kadang nomor acuan mesin dapat digunakan dalam transaksi input tanpa membutuhkan nomor konsumen ataupun nomor barang. Sebagai contoh, alamat berkas dari rekaman dapat dicetak pada buku tabungan langganan bank. Apabila komputer pemesan perusahaan penerbangan mengirimkan pesan teletip pada perusahaanpenerbangan yang lain, biasanya pesan itu mancakup nomor acuan mesin dari rekaman penumpang. Jawabandalam pesanan teletip diterima, misalnya tentang penegasan pemesanan, maka harus mencakup nomor acuan mesin, sehingga rekaman penumpang itu segera ditemukan.

Mode lokasi DIRECT dari CODASYL memakai teknik ini.

Teknik 7 : Alogaritma Untuk Konversi Kunci

Penggunaan algoritma untuk mengbah kunci ke dalam alamat, hampir secepat dengan teknik alamat setara kunci   (teknik 6). Alamat pada beberapa apilkasi dapat dihitung dari penciri entiti seperti lokasi jalan, nomor penerbangan dan tanggal penerbangan. Tidak semua aplikasi yang tidak menerapkannya. Tetapi metode ini adalah sederhana dan cepat untuk aplikasi yang dapat menerapkannya.

Teknik ini biasanya mempunyai kerugian karena tidak memenuhi barkas dengan sempurna. Ada celah- celahnya, karena kunci- kunci tidak diubah menjadi satu himpunan alamat yang kontinu. Sebagai contoh, perusahaan penerbangan mempunyai 150 nomor penerbangan. Algoritma memakai nomor penerbangan dan tanggal untuk menghitung alamat berkas. Tetapi tidak setiap penerbangan terbang pada setiap hari; karena itu, beberapa alamat yang dihasilkannya tidak memuat rekaman.

Apabila rekaman- rekaman membentuk suatu matrik, maka cocok untuk perhitungan alamat berkas. Sebagai contoh, suatu perusahaan mempunyai banyak distributor,. Masing- masing distributor menangani 200 produk. Rekaman yang diberikan adalah tentang penjualan setiap produk untuk setiap distributor dalam setiap distributor dalam setiap minggu untuk tahun ini. Apabila panjang rekaman 100 byte, maka alamat byte relatif dari rekaman untuk distributor ke-A, produk ke- B, dan minggu ke- C dapat dihitung dengan rumus:

(A -1) × 200 × 52 × 100 + (B− 1) × 52 × 100 + (C − 1) × 100 + 1. Suatu program akan mengubah alamat relatif ini ke dalam sebuah alamat mesin.

Kerugian dari pola ini pengalamatan langsung yakni kelakuannya. Sepaerti diketahui bahwa alamt mesin dpat berubah- ubah, karena berkas berkembang atau dipindahkan pada suatu unit yang lain atau berkas digabungkan atau dimodifikasi. Dalam hal ini pengalamatan langsung tidak dapat berjalan. Untuk menghilangkan sifat kekakuan ini pengalamatan langsung biasanya diselesaikan dalam dua tingkat. Tingkat pertama mengubah kunci menjadi suatu bilangan urut. Tingkat kedua mengubah bilangan urut itu menjadi alamt mesin. Apabila alamat mesin rekaman berbah, maka bilangan- bilangan urut yang dipakai tingkat kedua dapat dimodifikasi dengan mudah untuk menyesuaikan perubahan alamat mesin tersebut.

Mode lokasi CALC dari CODASYL memakai teknik ini.

Teknik 8 : Gabungan (Hashing)

Suatu bentuk yang bermanfaat dan akurat dari teknik perhitungan alamat disebut gabungan atau kadang- kadang disebut pengacakan (randomizing) atau pengadukan (scrambling). Dalam teknik ini kunci rinci diubah menjadi suatu bilangan hampir acak, dan bilangan ini dipakai untuk menentuksn di man rinci tersebut disimpan. Bilangan hampir acak itu dapat berhubungan dengan alamat di mana suatu rekaman disimpan. Cara ini ;lebih ekonomis, karena berhubungan dengansuatu area di mana suatu grup rekaman disimpan yang disebut sebagai bucket (keranjang), kadang- kadang disebut pocket (saku) atau slot. Jumalah rekaman nalari yang dapat disimpan dalam area ini disebut kapasitas bucket.

Apabila pada permulaan, berkas hendak diamati, lokasi dalam mana rekaman- rekaman disimpan ditentukan sebagai berikut:

  1. Kunci dari rekaman diubah menjadi suatu bilangan hampir acak, n, yang terletak dalam interval l sampai N, di mana N adalah jumlah bucket yang dapat dipakai untuk simpanan. Banyak algoritma gabungan memungkinkan operasi ini, dan harus dipilih satu yang sesuai dengan himpunan kunci dari rekaman- rekaman yang dibicarakan.
  2. Bilangan n diubah menjadi alamt dari bucket itu dibaca.
  3. Apabila ada sisa ruang dalam bucket itu, maka rekaman nalari dapat disimpan ke dalam bucket itu.
  4. Apabila bucket luapan (overflow). Ini dapat   sebagai urutan berikut, atau dapat sebagai suatu bucket pada area yang terpisah yang duihubungkan dengan pointer.

Apabila rekaman- rekaman hendak dibaca dari berkas, maka metode pencarian adalah sama dengan di atas , yaitu:

  1. Kunci dari rekaman yang akan dicari, diubah menjadi suatu bilangan hampir acak, yaitu n, dengan menggunakan algoritma yang sama.
  2. Bilangan n itu diubah menjadi alamat dari bucket ke- n, dan dan rekaman fisis di dalamnya dibaca.
  3. Bucket dicari untuk mendapatkan rekaman nalari yng diminta.
  4. Apabika rekaman yang diminta tiadak ada dalam bucket luapan dibaca dan di- search. Kadang- kadang perlu membaca lebih dari satu bucket luapan.

Teknik ini tidak akan mencapai kerapatan packing 100%, karena adanya sifat- sifat acak dari algoritma. Banyak Berkas dapat mencapai kerapatan packing 80%atau 90% dan tidak ada ruang yang diperlukan untuk index. Banyak rekaman dapat diperoleh dengansatu pencarian, tetapi ada yang memerlukan pencarian dalam satu detik, yaitu pada bucket luapan. Jarang diperlukan pencarian ketiga atau keempat.

Filed under Aku dan tulisanku, Dunia Komputer, Info Lain, Pemrograman, Perkuliahan
Tagged as , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,
Both comments and pings are currently closed.

1,044 Comments