Algoritma CVM terobosan menyelesaikan lebih daripada 40 tahun masalah pengiraan! Saintis komputer membelek syiling untuk mengetahui perkataan unik untuk 'Hamlet'

Mengira kedengaran mudah, tetapi sangat sukar untuk dilaksanakan dalam amalan.

Bayangkan anda dihantar ke hutan hujan tropika yang asli untuk menjalankan bancian hidupan liar. Setiap kali anda melihat haiwan, ambil gambar.

Kamera digital hanya merekodkan jumlah bilangan haiwan yang dikesan, tetapi anda berminat dengan bilangan haiwan yang unik, tetapi tiada statistik.

Jadi, apakah cara terbaik untuk mendapatkan haiwan unik ini?

Pada ketika ini, anda pasti akan berkata, mula mengira dari sekarang, dan akhirnya membandingkan setiap spesies baharu dari foto ke senarai.

Walau bagaimanapun, kaedah pengiraan biasa ini kadangkala tidak sesuai untuk jumlah maklumat sehingga berbilion-bilion penyertaan.

Para saintis komputer dari Institut Statistik India, UNL, dan Universiti Nasional Singapura telah mencadangkan algoritma baharu-CVM.

Ia boleh menganggarkan bilangan item berbeza dalam senarai panjang, dan hanya perlu mengingati sebilangan kecil item.

Alamat kertas: https://arxiv.org/pdf/2301.10191

Algoritma ini sesuai untuk mana-mana senarai di mana satu item dipaparkan pada satu masa, seperti teks dalam ucapan, barangan tali pinggang penghantar, Atau kereta di antara negeri.

Algoritma CVM dinamakan sempena huruf pertama tiga pengarang dan telah mencapai kemajuan yang ketara dalam menyelesaikan "masalah elemen berbeza".

Masalah ini telah menyusahkan saintis komputer selama lebih 40 tahun.

Ia memerlukan cara yang cekap untuk memantau aliran elemen (yang jumlah bilangannya mungkin melebihi memori yang tersedia) dan menganggarkan bilangan elemen unik di dalamnya.

Jadi, bagaimanakah algoritma CVM menyelesaikan masalah?

Merintis algoritma CVM, rahsianya terletak pada "rawak"

Andaikan anda sedang mendengar buku audio "Hamlet".

Drama ini mempunyai jumlah 30557 perkataan, berapa banyak yang berbeza?

Untuk mencari jawapan, anda boleh berhenti seketika semasa mendengar, tulis setiap perkataan dalam susunan abjad, kemudian langkau perkataan yang sudah ada dalam senarai, dan akhirnya, hanya kira setiap perkataan dalam senarai.

Kaedah ini boleh dilaksanakan, tetapi ia terlalu menguji "ingatan" seseorang.

Penyelidik Vinodchandran Variyam berkata, "Dalam situasi aliran data biasa, mungkin terdapat berjuta-juta item untuk dijejaki. Anda mungkin tidak mahu menyimpan semua maklumat.

Ini adalah, pelayan awan Di mana algoritma boleh menyediakan lebih mudah kaedah".

Caranya ialah "rawak".

Vinodchandran Variyam membantu mencipta algoritma CVM untuk menganggar bilangan elemen berbeza dalam aliran data

Berapa banyak perkataan unik yang terdapat dalam "Hamlet"? Coin Flip Challenge

Kembali ke "Hamlet", dengan mengandaikan bahawa "ingatan berkesan" anda hanya boleh memuatkan 100 patah perkataan.

Setelah audio mula dimainkan, anda menulis 100 perkataan pertama yang anda dengar dan melangkau sebarang perkataan yang berulang.

Apabila anda telah selesai merakam 100 perkataan, yang tinggal hanyalah melambungkan syiling untuk setiap perkataan –

Ketua, jaga perkataan. Jika ia adalah bahagian terbalik, padamkannya.

Selepas pusingan awal ini, anda akan ditinggalkan dengan kira-kira 50 perkataan yang berbeza.

Sekarang anda beralih kepada apa yang pasukan panggil Pusingan 1, teruskan membaca Hamlet dan menambah perkataan baharu.

Jika anda menemui perkataan sekali lagi yang sudah ada dalam senarai, balikkan syiling itu sekali lagi sehingga anda mempunyai 100 perkataan dalam papan putih ingatan anda.

Kemudian, kira-kira separuh daripada perkataan dipadam semula secara rawak berdasarkan keputusan 100 lambungan syiling. Pusingan 1 berakhir di sini.

Seterusnya, masuk pusingan kedua Pusingan 2.

Sama seperti pusingan pertama, kami akan meningkatkan kesukaran sesuatu perkataan - apabila anda menemui perkataan yang berulang, balikkan syiling itu semula.

Syaratnya, kalau ekor, padam macam dulu. Tetapi jika ia adalah kepala, balikkan syiling itu sekali lagi. Perkataan itu dikekalkan hanya apabila ia muncul sebagai kepala untuk kali kedua.

Setelah papan putih memori penuh, tamatkan pusingan dan kemudian padam kira-kira separuh daripada perkataan itu semula berdasarkan keputusan 100 lambungan.

Dalam Pusingan 3, anda perlu menyelak kepala syiling tiga kali berturut-turut untuk menyimpan perkataan.

Dalam pusingan keempat, simpan satu perkataan di hadapan empat kali berturut-turut, dan seterusnya.

Akhir sekali, pada pusingan ke-1, anda akan mendengar keseluruhan permainan "Hamlet".

Maksud latihan ini adalah untuk memastikan setiap perkataan mempunyai kebarangkalian kejadian yang sama: 1/2 (k).

Andaikan, pada penghujung audio Hamlet, anda mempunyai 61 perkataan dalam senarai anda dan ia mengambil masa enam pusingan untuk diselesaikan.

Anda boleh menganggarkan bilangan perkataan yang berbeza dengan membahagikan 61 dengan kebarangkalian 1/2 (6) - keputusan akhir dalam permainan ini ialah 3904.

Ketepatan algoritma adalah berkadar dengan jumlah memori

Penyelidik Chakraborty, Variyam dan Meel secara matematik membuktikan bahawa ketepatan algoritma CVM adalah berkadar dengan jumlah memori.

Dan Hamlet kebetulan mempunyai 3967 perkataan unik. (Dengan kaedah pengiraan biasa)

Dalam eksperimen menggunakan ingatan 100 perkataan, anggaran purata bagi 5 pusingan keputusan eksperimen ialah 3955 patah perkataan.

Dengan 1000 perkataan dalam ingatan, kapasiti memori purata meningkat kepada 3964.

Variyam berkata, "Jika (ingatan) cukup besar untuk menampung semua perkataan, maka kita boleh mencapai 100% ketepatan."

William Kuszmau dari Universiti Harvard berkata, "Ini adalah contoh yang bagus tentang bagaimana walaupun untuk masalah yang sangat asas dan dikaji secara meluas, kadangkala mungkin terdapat penyelesaian yang mudah tetapi tidak jelas masih perlu ditemui."