Memecahkan Actorle Dengan Python

Apa itu Aktor?

Actorle ialah teka-teki harian di mana Anda menebak nama seorang aktor dari petunjuk tentang pilihan film yang telah mereka bintangi. Anda perlu ketahui cukup banyak film sehingga Anda bisa menemukan elemen yang sama — seorang aktor yang muncul di semuanya. Ini permainan yang menyenangkan, dan saya sering memainkannya.

Sebuah ide terbentuk

Baru-baru ini saya mulai merenungkan pertanyaan: dapatkah saya membuat aplikasi Python untuk menyelesaikan Actorle dalam satu tebakan, 100% sewaktu-waktu?

Data aktor dan film yang mendasari permainan itu sepertinya berasal dari IMDb, Internet Movie Database. Saya bertanya-tanya apa kumpulan data ini ada untuk umum. Dengan akses ke data, itu pasti cuma masalah cari dan memfilter data itu untuk sampai pada jawabannya. Algoritme bisa dilihat seperti :

Make a list of sets
For each clue:
  Make a set for actors
  For each movie matching this clue:
    Find all actors that appeared in this movie
    Add those actors to the set
  Add the set to the list of sets
The answer is the intersection of all sets in the list

Tetapi bisakah kita mendapatkan datanya?

Ada API IMDb yang terlihat canggih, tapi selain uji coba satu bulan, itu tidak gratis untuk digunakan. Basis pengguna target jelas pengembang komersial, bukan orang yang meretas proyek mainan kecil untuk bersenang-senang. Kekecewaan.

Tetapi mungkin semuanya tidak hilang. Untuk peretasan non-komersial, ada subset yang ada untuk umum (lebih lanjut perihal utamanya menjadi subset) dari database IMDb. Menjanjikan!

Hollywood sebagai data

Dari membuat profile file yang diunduh menggunakan pustaka profile panda sumber terbuka yang luar biasa, saya sadari bahwa struktur datanya sangat relasional. Tiap file mungkin sesuai tabel yang berbeda di database relasional IMDb.

Saya ingin aplikasi saya mandiri, ditambah dataset yang berukuran relatif kecil, jadi dibanding memuat data terlebih dahulu ke database untuk diajak bicara oleh aplikasi saya, saya menentukan untuk membacanya ke panda pada waktu proses. Saya memilih untuk mengambil kinerja yang baik dengan imbalan ketergantungan aplikasi yang lebih sederhana.

Saya menyimpulkan bahwa saya hanya membutuhkan tiga file yang tersedia:

Movie data — File title.basics.tsv.gz berisi nilai yang akan kita gunakan saat mencari film yang cocok dengan petunjuk yang diberikan: judul (primaryTitle) dan tahun rilis (startYear).

Performances data — title.principals.tsv.gz memberi tahu kita orang mana yang mengerjakan produksi mana; ini ialah tabel link banyak-ke-banyak antara ID film (tconst) dan ID orang (nconst):

Actor data — name.basics.tsv.gz memetakan ID unik (nconst) ke nama orang (primaryName). Inilah cara kami menerjemahkan ID orang yang digunakan dalam tabel link ke nama aktor yang sebenarnya:

De-chonkifikasi data

Beberapa data yang tidak kami perlukan untuk kasus penggunaan pemecahan Actorle dicampur dengan data yang memang kami perlukan. Dengan resiko dituduh kerjakan pengoptimalan prematur, memotong bit asing itu akan membuat aplikasi kita menggunakan lebih sedikit memori, waktu pemrosesan, dan ruang disk.

Kami akan menyimpan semua kolom, tapi kehilangan beberapa baris.

Ada 9.446.373 baris dalam file title.basics.tsv.gz, tapi kami mengetahui dari laporan profil panda bahwa hanya sebagian kecil dari judul ini (629.554) yang sebenarnya ialah film. Actorle hanya menggunakan data film — tidak ada serial TV, episode TV, film pendek, dll. — sehingga kami bisa menghilangkan apa pun yang bukan film. Tidak ada yang peduli dengan acara TV Anda, gan.

Dari 3 file data yang akan kita gunakan, title.principals.tsv.gz — tabel link antara film dan orang yang mengerjakannya — sejauh ini ialah yang terbesar (c.405MB, versi c.230MB dan c.160MB), dan memiliki baris paling banyak sebanyak 53.573.733. Memfilter cuma untuk aktor (kategori=aktor|aktris) akan mengurangi jumlah baris hingga lebih dari setengahnya, menjadi kurang dari 21 juta.

Lumayan, tetapi kami belum selesai. Kami dapat memfilter semua penampilan aktor dalam judul yang bukan film, sehingga mengurangi jumlah baris jadi sekitar 2 juta untuk pengurangan keseluruhan lebih dari 95%. Tentu kami lebih ramping minggu ini!

Terakhir, ada 12.148.741 baris di name.basics.tsv.gz, tapi beberapa di antaranya bukan pemain; mungkin mereka sutradara, produser, atau operator kamera. Ada nyaris 8 juta non-aktor, dibandingkan dengan hanya di bawah 4,5 juta aktor. Kehilangan lebih dari 60% file ini terlihat seperti pengoptimalan yang bagus.

$ gzcat data/name.basics.tsv.gz | awk -F '\t' '{print $5}' | egrep "actor|actress" | wc -l
 4447196
$ gzcat data/name.basics.tsv.gz | awk -F '\t' '{print $5}' | egrep -v "actor|actress" | wc -l
 7701546

Saya membuat alat untuk mengunduh tiga file data, menerapkan filter ini menggunakan panda, dan menyimpan file yang diperkecil ke disk. Optimasi? Pasti. Prematur? Nah.

Menangani kesenjangan data

Saya sebutkan sebelumnya bahwa kami menggunakan subset dari database IMDb . Jadi apa yang hilang? Sepanjang yang saya dapat lihat dari banyak penelusuran di tempat, sepertinya tidak ada film yang benar-benar tidak ada, meskipun saya tidak jelas tentu.

Satu pemotongan yang pasti: setiap film memiliki maksimal tiga genre dalam data yang diunduh, dan di website IMDb dan Actorle Anda menemukan film dengan lebih dari tiga genre (contoh).

Saya memutuskan sejak awal untuk mengabaikan genre saat mencoba mencocokkan film dengan petunjuk, jadi tidak jadi masalah.

Data di title.principals.tsv.gz terlihat terpotong. Nampaknya hanya ada sedikit aktor¹ yang mencurigakan untuk banyak film, walau website IMDb mencantumkan puluhan aktor per film.

Sebagai contoh, film horor/thriller Dead Ringer karya David Cronenberg tahun 1988, (tt0094964 dalam database), memiliki 42 aktor menurut IMDb. Data kami tidak setuju — 38 orang perlu menghubungi agen mereka, karena mereka telah menghilang dari credit!

$ gzcat data/title.principals.tsv.gz | grep -i "tt0094964"

tt0094964 1 nm0000460 actor \N "[""Beverly"",""Elliot""]"
tt0094964 2 nm0000991 actress \N "[""Claire"",""Leo's wife(actress)""]"
tt0094964 3 nm0902794 actress \N "[""Cary"",""Elliot's girlfriend""]"
tt0094964 4 nm0329876 actress \N "[""Danuta"",""clinic receptionist""]"

Kesenjangan ini berpotensi lebih bermasalah. Jika kami menemukan film dari petunjuknya, tapi aktor yang kami cari tidak ada di data kami sama seperti yang muncul di film itu, kami mungkin dalam masalah.

Kami memiliki rencana untuk menggunakan satu set untuk menampung semua aktor kandidat untuk setiap petunjuk dan mengandalkan persimpangan dari semua set itu menjadi satu aktor. Sebagai hasil dari celah ini, beberapa dari set itu akan kehilangan aktor yang kita mencari, memberikan persimpangan ukuran 0 dan tidak ada jawaban untuk teka-teki tersebut. Anak panah yang buruk, bung.

Namun, kami mungkin baik-baik saja jika kami bisa mengubah algoritma kami untuk memberi kami toleransi untuk celah dalam data aktor/film. Kita tak perlu melihat aktor target untuk tiap petunjuk, mereka hanya perlu ada lebih sering secara keseluruhan daripada orang lain. Mengganti daftar set dengan daftar simpel mungkin berhasil:

Make a list
For each clue:
  For each movie matching this clue:
    Find all actors that appeared in this movie
    Add those actors to the list
The answer is the most common actor in the list

Tindakan!

Mengambil semua yang sudah saya pelajari mengenai data, saya menulis sebuah aplikasi baris perintah kecil yang menangkap teka-teki hari ini dari website Actorle.

Itu kemudian menggunakan panda untuk membaca data IMDb dan memanipulasinya sebagai tanggapan atas petunjuk, sampai kita mendapatkan daftar ID aktor yang tidak unik. Tiap elemen dalam daftar mewakili penampilan aktor dalam film yang mungkin merupakan jawaban dari salah satu wejangan. ID artis paling umum dalam daftar ialah aktor yang kami cari.

Anda bisa menemukan code di GitHub.

Nah, apa itu berhasil?

Anda betcha! Saya telah mencobanya pada 70 atau 80 teka-teki dan tidak gagal. Anda bisa melihat alat ini beraksi, memecahkan teka-teki harian nyata, dalam video Asciinema singkat ini.

Kenyataannya, ini bekerja dengan sangat baik hingga sekarang saya menggunakannya hanya pada teka-teki yang telah saya pecahkan, jika tidak, itu akan menyedot semua kesenangan dari Actorle. Saya telah menciptakan monster. Saya begitu repot dengan apa saya bisa, saya tidak berhenti untuk berpikir apa saya harus…

Berteriaklah jika ingin lebih cepat

Pengurangan ukuran data dari c.800MB menjadi c.135MB menurunkan waktu pemecahan teka-teki dari lebih dari 3 menit menjadi 20-30 detik. Kinerja tidak terlalu penting di sini, dan saya cukup yakin aplikasi saya akan menendang pantat saya dalam deathmatch Actorle sekitar 100% dari waktu, tapi itu tetap agak lambat.

Sebagian besar waktu dihabiskan oleh panda untuk membaca data dari disk dan mengindeksnya di memori. Saya dapat memotong lebih banyak data — lagipula ada seluruh kolom yang tidak saya gunakan — tapi aplikasi akan relatif lambat saat membaca di kumpulan data setiap kali dijalankan.

Pendekatan go-faster yang jelas ialah memuat data ke database relasional dan membuat kueri aplikasi saya itu, daripada memanipulasi data tersebut dalam proses. Itu kemungkinan akan mengarah pada urutan pengurangan besaran dalam waktu berjalan. Saya mungkin membahasnya dalam posting tindak lanjut beberapa waktu mendatang.

Ringkasan

Dalam posting ini kami memperkenalkan Actorle, teka-teki terkait film harian. Kami menganalisis kumpulan data IMDb yang tersedia untuk umum untuk menilai kesesuaiannya untuk memecahkan teka-teki Actorle, mencatat potensi kesenjangan yang signifikan dalam data. Kami menjelaskan pendekatan pra-pemrosesan untuk mengoptimalkan kumpulan data menggunakan pemfilteran baris dasar.

Kami kemudian menulis beberapa code Python untuk menginterogasi kumpulan data untuk memecahkan teka-teki Actorle, memakai algoritme yang dirancang untuk mentolerir celah dalam data.

Terakhir, kami membahas perubahan pendekatan yang dapat mengarah pada peningkatan kinerja yang signifikan di kala mendatang.