👳🏿 🚶🏻 📪 Hans Peter Lun dan kelahiran algoritma hash 👩‍🎓 💦 🔬

Algoritme hash dari seorang insinyur IBM memberi komputer kemampuan untuk dengan cepat mencari dokumen, DNA, dan database

Mulai tahun 1940-an, Lun mengembangkan mesin dan sistem untuk menganalisis informasi, khususnya algoritma hash yang saat ini banyak digunakan, yang ia usulkan sebagai metode penyortiran. angka dan teks.

Pada November 1958 , selama konferensi internasional enam hari mengenai informasi ilmiah, penemu Hans Peter Lun mendemonstrasikan beberapa mesin elektromekanis. Mereka terlihat sangat biasa. Seperti semua perangkat komputasi lain pada waktu itu, mereka bersudut, praktis dan dirancang untuk menerima dan mengurutkan tumpukan kartu punch dalam slot dan keranjang.

Namun, tidak seperti komputer lain, perangkat Bulan tidak bekerja dengan angka dan formula, tetapi dengan kata-kata dan kalimat. Salah satu mesin yang menarik perhatian khusus menggunakan algoritma Bulan yang disebut KWIC, Key for Word in Context . Setelah menerima sejumlah besar teks - misalnya, artikel dari 500 hingga 5.000 kata, KWIC dapat dengan cepat dan mandiri membangun sesuatu seperti indeks.

Pada saat itu, pengindeksan, klasifikasi, dan pengorganisasian informasi secara tertulis merupakan proses yang sangat memakan waktu, bahkan bagi para profesional yang berpengalaman. Dan volume informasi di beberapa daerah tumbuh terlalu cepat untuk mendukungnya. Sangat membutuhkan alat baru yang lebih baik untuk abstrak dan generalisasi. Untuk pustakawan dan ilmuwan informasi yang berkumpul di Washington, demonstrasi KWIC mirip dengan gempa bumi. Surat kabar di seluruh negeri segera menulis tentang penemuan luar biasa Bulan.

Pada awal 1960-an, KWIC telah menjadi dasar untuk pengembangan ratusan sistem pengindeksan terkomputerisasi, termasuk yang digunakan oleh Layanan Abstrak Kimia, Abstrak Biologis dan Institut Informasi Ilmiah. Beberapa ahli menyebut pengembangan KWIC "peristiwa terbesar dalam dunia kimia sejak penemuan tabung reaksi." Lun, insinyur senior IBM, juga membangun "sistem pintar" untuk bisnis dengan KWIC. (Catatan: dialah yang pertama kali mengusulkan istilah BI). Dia dapat mengidentifikasi dan memberikan informasi yang relevan kepada individu-individu tertentu dari perusahaan besar. Intinya, KWIC adalah setara dengan mesin pencari pada saat itu: KWIC memungkinkan pengguna untuk dengan cepat menemukan informasi yang mereka butuhkan.

Sekarang kami menerima begitu saja bahwa komputer dapat bekerja dengan informasi dan langsung menawarkan ulasan restoran, hasil olahraga, dan harga saham kepada kami. Pada zaman bulan, komputer itu sederhana dan primitif. Usahanya untuk bekerja dengan teks membantu membentuk pandangan yang lebih luas tentang komputer dan kemampuan mereka. Dan idenya masih menjadi dasar dari algoritma yang kami gunakan untuk belanja online, terjemahan mesin dan penelitian genetik. Tentu saja, pada 1950-an semua ini benar-benar tidak terpikirkan. Selanjutnya, kita akan berbicara tentang apa yang menyebabkan fungsi hash bulan, solusi untuk masalah yang bahkan tidak ada.

Tahun-tahun setelah Perang Dunia IImemiliki dampak besar pada perangkat komputasi elektronik. Berbagai mesin tahun-tahun perang melakukan perhitungan vital untuk balistik, senjata atom, dan kriptografi. Perang Dingin berikutnya memberikan pengembang komputer dengan pendanaan berkelanjutan, dan sebagai hasilnya, mesin menjadi lebih cepat, lebih akurat dan lebih kuat. Tetapi tujuan utama mereka - memproses dan menyimpan angka - tetap tidak berubah.

Di dunia komputer yang baru lahir, Lun adalah karakter yang tidak biasa. Selalu memiliki selera pakaian yang bagus, Lun lebih memahami industri tekstil daripada ilmu komputer. Dia datang untuk bekerja di IBM pada tahun 1941. Sejumlah penemuan Bulan, tampaknya, masih termasuk dalam era pra-digital kalkulator mekanik dan aturan geser. Bahkan komputer digital pada 1950-an lebih kuat daripada perangkat elektromekanisnya. Namun demikian, ide-ide Bulan, satu atau lain cara dipikirkan kembali dan diubah, sekarang diterapkan di hampir semua jenis perangkat lunak.

Hans Peter Lun lahir pada tahun 1896 di kota Barman, Jerman. Ayahnya, Johann Lun, seorang pencetak yang sukses, sangat setia pada hobi anak-anaknya. Misalnya, suatu kali Hans, bersama saudara-saudaranya, membangun kereta api mini di taman keluarga. Rel timbal 70 meter dilebur ke mesin ayahnya.

Setelah lulus dari sekolah, Lun belajar kerajinan keluarga di Swiss. Tetapi Perang Dunia Pertama dan wajib militer di tentara Jerman mengganggu karier cetaknya. Setelah perang, Lun mulai berdagang tekstil. Di Amerika Serikat, ia mendapati dirinya pada tahun 1924 mencari tempat-tempat potensial untuk pembangunan pabrik-pabrik tekstil. Dan bahkan dalam bisnis tekstil, vena inventif bulan telah menemukan aplikasi. Pada tahun 1927, ia mengembangkan garis khusus yang memungkinkan untuk menghitung jumlah benang pada kain.Lunometer masih dijual oleh HP Luhn & Associates, sebuah perusahaan teknik dan konsultasi yang didirikan oleh Moon.

Lun belajar dengan cepat. Dia benar-benar menyerap pengetahuan dari berbagai bidang dan secara bertahap menjadi pendaki yang berpengalaman, spesialis kuliner gourmet dan pelukis lanskap yang baik. Pada 1930-an, daftar patennya yang luas termasuk: jubah lipat , alat untuk membentuk stoking wanita, meja permainan, dan Cocktail Oracle - panduan yang membantu pengguna membuat koktail dari apa yang ada di tangan.

Pada tahun 1933, sesaat sebelum akhir Larangan, Lun mengajukan paten untuk panduan yang membantu membuat koktail bahan tersedia.

Tetapi yang terpenting, Bulan tertarik pada penyimpanan, transmisi, dan pengambilan informasi, terutama informasi tekstual. Sebenarnya, minat ini membawanya ke IBM, di mana ia menerima "gelar" penemu. Lun ternyata sangat luar biasa produktif - selama karirnya, ia menciptakan sekitar 70 paten untuk IBM. Terlepas dari kenyataan bahwa tidak ada yang membatasi dirinya dalam pilihan tugasnya, banyak penemuannya berpusat di sekitar penggunaan mesin, termasuk yang elektronik, untuk memanipulasi informasi.

Sebagai contoh, pada tahun 1946 dan 1947, Lun bekerja untuk mengajar mesin untuk "membaca" dokumen yang diketik pada mesin tik. Salah satu perangkatnya terdiri dari selotip logam yang dimasukkan ke dalam mesin tik yang menerapkan kode magnetik pada kertas. Kemudian mesin lain dapat memindai mereka. Beberapa saat kemudian, ia, bersama dengan dua ahli kimia dari MIT, Malcolm Dyson dan James Perry, mulai mengerjakan mesin yang secara otomatis dapat mencari senyawa kimia menggunakan kartu punch. Setiap kartu punch dikodekan dengan informasi tentang koneksi tertentu. Pengguna harus memasukkan "kartu permintaan" ke dalam mesin dan menunjukkan serangkaian kriteria yang diperlukan untuk membandingkan dan mengurutkan kartu komposit. Pemindai tersebut ternyata sangat terspesialisasi, dan Lun terus mencari cara yang lebih universal untuk pemrosesan informasi otomatis.

Masalah informasi pada tahun-tahun itu ada di bibir semua orang. Pada periode pascaperang, jumlah publikasi ilmiah dan teknis meningkat tajam. Banyak ahli khawatir bahwa bisnis dan sains akan jatuh karena kelebihan informasi. Vannevar Bush , selama perang, pemimpin departemen ilmiah utama Amerika dan salah satu penggagas penciptaan National Science Foundation, mengusulkan alat elektromekanis Memex berukuran meja untuk menyimpan dan menghubungkan informasi.

Proposal Bush tidak pernah terwujud, tidak seperti ide Moon. Misalnya, pada 6 Januari 1954, ia mengajukan paten untuk Komputer untuk Memeriksa Nomor.. Itu adalah alat mekanik manual yang dirancang untuk memecahkan masalah praktis yang sederhana. Pada saat itu, berbagai jenis nomor identifikasi, seperti nomor kartu kredit dan nomor jaminan sosial, mulai memainkan peran besar dalam kehidupan publik dan pribadi. Namun, jumlahnya sulit untuk diingat, mereka bisa salah didekripsi atau sengaja dipalsukan. Diperlukan cara untuk memverifikasi kebenaran nomor identifikasi dengan cepat.

Mesin seukuran kantong, bulan, hanya tentang itu. Dia bekerja berdasarkan algoritma checksum yang dia kembangkan. Untuk nomor 10 digit, komputer melakukan tindakan berikut:

dua kali lipat setiap digit kedua;
jika ada hasil yang lebih besar dari atau sama dengan 10, tambahkan digit hasil ini untuk mendapatkan angka satu digit (misalnya, "16" akan menjadi 1 + 6 = 7);
tambahkan semua 10 digit nomor baru;
kalikan dengan 9;
ambil digit terakhir dari hasil ini.

Algoritma ini menghasilkan nomor verifikasi unik. Dalam formulasi asli bulan, "0" berarti bahwa nomor aslinya adalah nyata. Dalam versi selanjutnya, nomor verifikasi hanya ditambahkan ke nomor asli dalam bentuk digit terakhir, dan mudah untuk memeriksa apakah digit terakhir sesuai dengan hasil pemeriksaan pada mesin Bulan. Urutan dasar perhitungan, sekarang dikenal sebagai Algoritma Bulan, masih banyak digunakan. Ini memverifikasi jumlah pengidentifikasi peralatan seluler internasional (IMEI) yang ditetapkan untuk ponsel.

Tetapi jauh lebih penting bahwa salah satu algoritma terpenting dari era digital berasal dari roda gigi dan roda mesin Bulan: hashing. Algoritme kelas luas ini menawarkan cara yang kuat untuk mengatur informasi sehingga komputer dapat dengan mudah menemukannya. Ini mirip dengan resep kornet dan kentang: algoritma hash, seperti koki, membagi dan mencampur data dengan berbagai cara. "Kebingungan" seperti itu dengan penyebaran yang tepat dapat mempercepat banyak jenis operasi komputer.

Pada awal 1953, Lun mengirim catatan internal ke IBM, di mana ia menyarankan memasukkan informasi dalam "ember" (ember - ember, keranjang) untuk mempercepat pencarian. Misalkan Anda perlu menemukan nomor telepon di basis data dan mencari tahu milik siapa. Ini terdiri dari 10 angka: "314-159-2652." Komputer akan dapat memeriksa satu nomor dari database pada satu waktu sampai menemukan entri yang diinginkan. Namun, jika database berisi jutaan angka, itu akan memakan banyak waktu.

Gagasan Bulan adalah untuk mengatur semua entri dalam keranjang bernomor. Ini dilakukan sebagai berikut: digit nomor telepon dikelompokkan berpasangan (dalam hal ini, 31, 41, 59, 26, 52). Kemudian pasangan angka ditambahkan (4, 5, 14, 8, 7), dan nomor baru dihasilkan dari mereka. Jika hasil penambahan di dalam pasangan berisi dua digit, hanya yang terakhir diambil (yaitu, ternyata 45.487). Nomor telepon asli dan nama / alamat yang sesuai dengan itu akan ditempatkan di keranjang dengan nomor 45487.

Pencarian berdasarkan nomor telepon terdiri dalam menghitung nomor keranjang (menggunakan metode Bulan) dan kemudian mengekstraksi informasi dari keranjang ini. Bahkan jika grup berisi beberapa catatan, pencarian di antara mereka jauh lebih cepat daripada pencarian di seluruh database.

Selama beberapa dekade, ilmuwan dan pemrogram komputer telah menyempurnakan metode Bulan dan menemukan kegunaan baru bagi mereka. Tetapi ide dasarnya tetap sama: gunakan matematika untuk mengatur data menjadi kelompok yang mudah ditemukan. Karena masalah pengorganisasian dan pencarian data sangat umum dalam teknologi komputer, algoritma hashing menjadi sangat diperlukan dalam kriptografi, grafik, telekomunikasi dan biologi. Setiap kali Anda mengirim nomor kartu kredit melalui Internet atau menggunakan kamus editor teks, fungsi hash berfungsi.

Pengindeksan Cepat: Pada Konferensi Internasional 1958 tentang Informasi Ilmiah, Hans Peter Lun (kanan) menunjukkan sistem IBM untuk secara otomatis membuat indeks dokumen berdasarkan algoritma KWIC yang dikembangkannya.

Ide Bulan dalam Ilmu Komputerjauh melampaui pencarian biasa. Dia menyadari bahwa komputer mampu melakukan manipulasi kompleks dengan teks: membaca dan memahami bahasa tertulis. Pengindeksan dan pengorganisasian informasi selanjutnya untuk memecahkan masalah praktis dalam sains dan bisnis. Pada tahun 1958, penyortir kartu kimianya telah menjadi Universal Card Scanner dan 9900 Special Index Analyzer, yang diperagakan di konferensi Washington. Perangkat elektromekanis ini dapat mencari dan mengurutkan kartu punch sesuai dengan kriteria pengguna.

Tetapi sebagian besar kebisingan dibuat oleh KWIC, sistem Bulan untuk membangun konkordansi. Konkordansi adalah daftar kata kunci menurut abjad yang digunakan dalam buku atau kumpulan karya. Itu terlihat seperti glosarium, tetapi daftar hanya kata-kata yang benar-benar muncul dalam teks, dan bukan konsep. Kata-kata yang tidak membawa muatan semantik, seperti preposisi, kata sambung dan artikel, tidak masuk dalam konkordansi. Konkordansi telah lama digunakan dalam teologi dan filologi. Misalnya, konkordansi Alkitab akan menunjukkan setiap penggunaan kata "cinta" dengan merujuk pada sebuah buku, bab, dan ayat. Sebelum pencarian terkomputerisasi teks lengkap muncul, membuat konkordansi adalah proses yang memakan waktu. Lebih sering daripada tidak, konkordansi diciptakan untuk karya-karya "penting", seperti Alkitab atau karya-karya Shakespeare yang dikumpulkan.

Apa yang pernah dilakukan sistem Bulan untuk mencari berdasarkan angka, KWIC lakukan untuk teks. Yang satu dan yang lainnya memungkinkan untuk mencari informasi dalam volume besar dengan mudah. Ambil contoh yang sangat sederhana. Misalkan Anda ingin membuat konkordansi dari kata-kata dalam judul empat buku berikut: Gone With the Wind, War and Peace, Shadow of the Wind, dan Shadow of War. (Catatan: dalam dokumen asli - Gone With the Wind, War and Peace, The Shadow of the Wind, dan Shadows of War)

Algoritma KWIC akan mengatur ulang kata-kata dari nama-nama dalam semua pesanan yang mungkin, dan kemudian mengatur setiap permutasi secara alfabet. Hasilnya akan menjadi daftar kata kunci lengkap (yaitu, semuanya kecuali preposisi, kata sambung dan artikel) dalam konteks di mana mereka muncul.

Sistem KWIC Moon dengan cepat menemukan aplikasi di komunitas ilmiah. Tetapi dia tahu bahwa itu akan berguna untuk bisnis juga. Pada tahun 1958, ia menulis sebuah artikel untuk IBM Journal of Research and Development yang berjudul "A Business Intelligence System". Di dalamnya, ia mengusulkan suatu sistem yang dapat secara otomatis menghasilkan abstrak artikel, mengekstraksi ide-ide kunci dari abstrak, dan kemudian mengirimkan hasilnya kepada karyawan perusahaan yang sesuai. Lun memahami bahwa menyelesaikan masalah kelebihan informasi berarti mengembangkan metode untuk menyortir informasi dengan cepat yang tidak akan membebani orang dengan bahan berlebih.

The New York Times dalam sebuah obituari tahun 1964, Luna menggambarkan sistem abstraknya sebagai berikut:

Scientific American 2326 , IBM . , ...

Program abstraksi Luna pertama-tama menghitung frekuensi semua kata dalam artikel. Setelah membuang kata-kata yang sangat umum, "abstrak" menemukan kalimat di mana beberapa kata yang paling sering muncul bersamaan. Proposal seperti itu dianggap representatif dan ditempatkan secara abstrak. Itu adalah metode statistik murni yang tidak berusaha untuk "memahami" kata-kata dalam artikel atau hubungan di antara mereka. Tetapi, seperti KWIC, ia menunjukkan bahwa komputer dapat secara efektif digunakan untuk mengatur teks menjadi format yang mudah dibaca.

Lun meninggalkan IBM pada tahun 1961dan tiga tahun kemudian dia meninggal karena leukemia. Dia tidak hidup untuk melihat hari ketika perubahan besar terjadi di Internet. Tidak termasuk lingkaran kecil spesialis informasi, pekerja tekstil dan sejarawan, hanya sedikit orang yang ingat namanya. Tapi ide-ide tentang bulan hidup. Hari ini, hashing memainkan banyak peran dalam mengelola dan melindungi kehidupan digital kita. Saat Anda memasukkan kata sandi di situs web, server kemungkinan besar menyimpan versi kata sandi yang di-hash. Saat Anda berinteraksi dengan situs menggunakan protokol https aman atau membeli sesuatu menggunakan bitcoin, hash juga berfungsi di sana. Dengan layanan cloud seperti Dropbox dan Google Drive, hashing membantu membuat penyimpanan dan berbagi file jauh lebih efisien. Dalam genetika dan penelitian teknologi tinggi lainnya, hashing secara signifikan mengurangi waktu yang dibutuhkan untuk menganalisis sejumlah besar data.

Hash mengubah komputer menjadi alat "tekstual" yang dapat diucapkan dengan huruf dan kata. Google Translate, Google N-gram, Google AdWords, dan Google Search semuanya dengan satu atau lain cara didedikasikan untuk menemukan makna teks. Ledakan informasi di Internet telah menjadikan pembacaan otomatis dan pemahaman [berita dan informasi lain] sebagai prioritas untuk bisnis, untuk ilmu pengetahuan, untuk semua orang. Pengembangan hash telah dikaitkan dengan teks dan merupakan refleksi dari pemikiran Lun tentang kata-kata, kalimat, konkordansi, kutipan, indeks, dan intisari.

Ini adalah warisan Luna: dia membantu menunjukkan bahwa kalkulator dan perhitungan tidak hanya domain matematika, statistik dan logika, tetapi juga bahasa, linguistik, dan sastra. Pada saat itu, itu adalah cara revolusioner dalam memandang mesin.

Sejarawan teknologi Michael Mahoneydisebut komputer "mesin steroid": "bukan hanya satu hal, tetapi banyak hal, mesin yang dapat diasah untuk tujuan apa pun. Bahkan sekarang, kita cenderung melihat komputer dalam arti sempit sebagai prosesor digital raksasa yang melakukan jutaan perhitungan dan operasi per detik. Pandangan Hans Peter Moon pada komputer diperluas. Menyadari bahwa komputer ini memiliki banyak segi, ia telah membantu membuka cakrawala baru yang menjanjikan untuk penelitian. ”

Hans Peter Lun dan kelahiran algoritma hash

More articles: