Pola penghitungan

Peta frekuensi (frequency map) adalah pola hashing yang paling sering dipakai, cukup satu lintasan untuk menghitung berapa kali setiap butir muncul, lalu jawaban banyak soal mengikutinya. Topik ini membangun pola tersebut dengan dict biasa dan Counter, menerapkannya pada deteksi anagram, lalu menurunkan dua pola yang lazim muncul di soal, pengelompokan anagram dan pencarian mayoritas. Bagian akhir menyediakan kumpulan soal latihan yang semuanya tuntas dengan pola-pola yang sama.

Peta frekuensi satu lintasan#

Peta frekuensi adalah dict yang kuncinya butir data dan nilainya banyaknya kemunculan. Membangunnya hanya butuh satu lintasan, untuk setiap butir naikkan penghitungnya, dan butir yang belum ada cukup dimulai dari nol. Pola ini berbiaya $O(n)$ waktu dan $O(k)$ ruang untuk $k$ butir unik, jauh lebih murah daripada membandingkan setiap butir dengan seluruh butir lain yang berbiaya $O(n^2)$. Demo berikut menghitung frekuensi huruf dan kata, sekaligus memperkenalkan Counter dari pustaka bawaan.

"""Peta frekuensi dibangun dalam satu lintasan, untuk karakter dan kata."""

from collections import Counter

teks = "statistika"

# cara manual: dict biasa, setiap karakter dikunjungi tepat satu kali
frekuensi = {}
for huruf in teks:
    frekuensi[huruf] = frekuensi.get(huruf, 0) + 1
print("dict manual :", frekuensi)

# cara Counter: pustaka bawaan, satu baris untuk pekerjaan yang sama
print("Counter     :", Counter(teks))
print("terbanyak   :", Counter(teks).most_common(3))

kalimat = "burung merpati dan burung kakatua hinggap di pohon"
print("hitung kata :", Counter(kalimat.split()))

dict manual : {'s': 2, 't': 3, 'a': 2, 'i': 2, 'k': 1}
Counter     : Counter({'t': 3, 's': 2, 'a': 2, 'i': 2, 'k': 1})
terbanyak   : [('t', 3), ('s', 2), ('a', 2)]
hitung kata : Counter({'burung': 2, 'merpati': 1, 'dan': 1, 'kakatua': 1, 'hinggap': 1, 'di': 1, 'pohon': 1})

Cara manual dengan get(huruf, 0) + 1 dan cara Counter menghasilkan peta yang sama, bedanya hanya penulisan. Counter menambahkan bonus berupa most_common, yang mengembalikan butir dengan frekuensi tertinggi tanpa pengurutan manual, dan cetakannya pun otomatis berurut dari frekuensi tertinggi. Penghitungan kata pada kalimat memakai pola yang sama persis, cukup ganti karakter dengan hasil pemenggalan kalimat. Perhatikan bahwa cetak dict manual mengikuti urutan kemunculan pertama, sifat dict yang membuat keluaran demo dapat diandalkan.

Deteksi anagram#

Anagram adalah kata yang tersusun dari huruf-huruf yang sama persis, termasuk banyaknya tiap huruf, misalnya “tunas” dan “sutan”. Dua kata adalah anagram tepat ketika peta frekuensinya identik, sehingga soal deteksi anagram berubah menjadi perbandingan dua peta. Cara pertama membangun dua peta lalu membandingkannya, sedangkan cara kedua memakai satu peta, menaikkan penghitung untuk huruf kata pertama dan menurunkannya untuk huruf kata kedua. Pasangan itu dinyatakan anagram hanya bila seluruh penghitung kembali nol, tanpa sisa yang terlewat maupun penghitung negatif.

"""Deteksi anagram dengan peta frekuensi, dua varian."""

from collections import Counter


def anagram_dua_peta(kata1, kata2):
    """Bandingkan peta frekuensi lengkap dua kata."""
    frek1, frek2 = {}, {}
    for huruf in kata1:
        frek1[huruf] = frek1.get(huruf, 0) + 1
    for huruf in kata2:
        frek2[huruf] = frek2.get(huruf, 0) + 1
    return frek1 == frek2


def anagram_satu_peta(kata1, kata2):
    """Satu peta, penghitung naik untuk kata1 dan turun untuk kata2."""
    if len(kata1) != len(kata2):
        return False
    frek = {}
    for huruf in kata1:
        frek[huruf] = frek.get(huruf, 0) + 1
    for huruf in kata2:
        if huruf not in frek:
            return False           # huruf yang tak pernah muncul di kata1
        frek[huruf] -= 1
        if frek[huruf] == 0:
            del frek[huruf]        # penghitung habis, bersihkan
    return len(frek) == 0


pasangan = [("tunas", "sutan"), ("tunas", "tanam")]
for kata1, kata2 in pasangan:
    hasil1 = anagram_dua_peta(kata1, kata2)
    hasil2 = anagram_satu_peta(kata1, kata2)
    print(f"{kata1} vs {kata2}: dua peta = {hasil1}, satu peta = {hasil2}")

print("Counter     :", Counter("tunas") == Counter("sutan"))

tunas vs sutan: dua peta = True, satu peta = True
tunas vs tanam: dua peta = False, satu peta = False
Counter     : True

Varian satu peta menolak lebih awal, huruf yang tidak ada dalam peta atau penghitung yang sudah nol langsung memutuskan bukan anagram tanpa menyapu sisa kata. Pemeriksaan panjang di awal juga menyaring kasus yang mustahil sebelum perulangan dimulai. Kedua varian tetap berbiaya $O(n)$ untuk kata sepanjang $n$. Perbandingan penuh lewat Counter cocok untuk tulisan pertama yang cepat jadi, sedangkan varian satu peta menerjemahkan lebih langsung ke bahasa lain, sebagaimana diperlihatkan versi Javanya di bagian akhir topik.

Pola turunan dari peta frekuensi#

Banyak soal tidak berhenti pada penghitungan, tetapi memakai peta frekuensi sebagai pijakan. Pola pertama adalah pengelompokan anagram, kuncinya dibuat kanonik dengan mengurutkan huruf setiap kata, sehingga kata-kata yang merupakan anagram saling menghasilkan kunci yang sama dan berkumpul dalam satu list. Pola kedua adalah pencarian mayoritas, elemen yang muncul lebih dari setengah banyaknya data, dan cukup dicari pada peta frekuensi dengan satu pemeriksaan per butir. Demo berikut menjalankan keduanya dalam satu program.

"""Dua pola turunan peta frekuensi, mengelompokkan anagram dan mencari mayoritas."""

kata = ["sapi", "kutu", "pisa", "tuku", "pasi", "ukut", "malam"]

# pola 1: kunci kanonik dari huruf-huruf yang diurutkan
kelompok = {}
for k in kata:
    kunci = "".join(sorted(k))
    kelompok.setdefault(kunci, []).append(k)

for kunci in sorted(kelompok):     # kunci diurutkan agar keluaran pasti
    print(kunci, ":", kelompok[kunci])

# pola 2: mayoritas, elemen yang muncul lebih dari setengah banyaknya data
nilai = [3, 3, 4, 2, 3, 3, 5, 3]
frek = {}
for v in nilai:
    frek[v] = frek.get(v, 0) + 1

for v, c in frek.items():
    if c > len(nilai) // 2:
        print("mayoritas :", v, "muncul", c, "dari", len(nilai), "nilai")

aalmm : ['malam']
aips : ['sapi', 'pisa', 'pasi']
ktuu : ['kutu', 'tuku', 'ukut']
mayoritas : 3 muncul 5 dari 8 nilai

Kunci kanonik “aips” mengumpulkan sapi, pisa, dan pasi dalam satu kelompok, meskipun tiga kata itu tidak tampak serupa sebelum hurufnya diurutkan. Kunci semacam ini adalah ide penting, kesetaraan yang rumit diubah menjadi perbandingan string sederhana. Pada pencarian mayoritas, angka 3 muncul lima kali dari delapan nilai sehingga melampaui setengah banyaknya, dan pemeriksaan itu dilakukan setelah peta selesai dibangun. Kelompok dicetak dalam urutan kunci yang diurutkan supaya keluarannya pasti sama setiap kali dijalankan.

Penghitungan pada Java#

Java tidak punya Counter, tetapi metode merge pada HashMap menuliskan pola penghitungan dalam satu baris, naikkan nilai lama sebesar satu atau mulai dari satu bila kuncinya baru. Metode yang sama dipakai untuk karakter pada pemeriksaan anagram maupun angka pada pencarian mayoritas, sehingga satu cara menaungi keduanya. Program berikut mengulang deteksi anagram dan pencarian mayoritas untuk memperlihatkan padanannya.

import java.util.HashMap;
import java.util.Map;

public class PolaHitung {
    // anagram diperiksa dengan satu peta, penghitung naik lalu turun
    static boolean anagram(String a, String b) {
        if (a.length() != b.length()) {
            return false;
        }
        Map<Character, Integer> frek = new HashMap<>();
        for (char c : a.toCharArray()) {
            frek.merge(c, 1, Integer::sum);
        }
        for (char c : b.toCharArray()) {
            Integer sisa = frek.get(c);
            if (sisa == null || sisa == 0) {
                return false;
            }
            frek.put(c, sisa - 1);
        }
        for (int sisa : frek.values()) {
            if (sisa != 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println("anagram tunas-sutan : " + anagram("tunas", "sutan"));
        System.out.println("anagram tunas-tanam : " + anagram("tunas", "tanam"));

        int[] nilai = {3, 3, 4, 2, 3, 3, 5, 3};
        Map<Integer, Integer> frek = new HashMap<>();
        for (int v : nilai) {
            frek.merge(v, 1, Integer::sum);
        }
        int mayoritas = -1;
        for (Map.Entry<Integer, Integer> e : frek.entrySet()) {
            if (e.getValue() > nilai.length / 2) {
                mayoritas = e.getKey();
            }
        }
        System.out.println("mayoritas           : " + mayoritas);
        System.out.println("frekuensinya        : " + frek.get(mayoritas) + " dari " + nilai.length);
    }
}

anagram tunas-sutan : true
anagram tunas-tanam : false
mayoritas           : 3
frekuensinya        : 5 dari 8

Metode merge(c, 1, Integer::sum) membaca, kunci c bertambah satu terhadap nilai lamanya, atau bernilai satu ketika belum ada. Pada fungsi anagram, penghitung yang sudah habis dipakai menjadi penolakan lebih awal, sama seperti varian satu peta pada Python. Berbeda dari versi Python yang menghapus entri saat penghitungnya nol, versi Java membiarkan entri berisi nol dan memeriksanya pada penyapuan terakhir. Pencarian mayoritas menyapu entrySet untuk menemukan kunci dengan nilai lebih dari setengah banyaknya, dan hasilnya deterministik karena hanya satu kunci yang mampu melampaui ambang itu.

Soal untuk dipraktikkan#

Delapan soal berikut seluruhnya tuntas dengan peta frekuensi, hash set, atau hash map yang dibedah sepanjang modul ini.

1. Valid Anagram : soal deteksi anagram persis seperti yang dikerjakan di topik ini, cukup bandingkan dua peta frekuensi.
2. Ransom Note : memakai varian satu peta dengan pengurangan penghitung untuk memeriksa ketersediaan huruf.
3. Group Anagrams : menerapkan kunci kanonik dari huruf terurut untuk mengumpulkan kata-kata yang setara.
4. Contains Duplicate : soal keanggotaan hash set yang paling murni, cukup satu lintasan dengan pemeriksaan in.
5. Intersection of Two Arrays : memotong dua kumpulan nilai dengan dua hash set dan pemeriksaan keanggotaannya.
6. Top K Frequent Elements : peta frekuensi menjadi pijakan, lalu k teratas diambil dengan pengurutan atau heap.
7. Majority Element : pencarian mayoritas yang sama dengan demo topik ini, frekuensi lebih dari setengah banyaknya data.
8. Isomorphic Strings : memperluas peta frekuensi menjadi peta pemetaan huruf ke huruf pada dua string.

Ringkasan#

• Peta frekuensi dibangun satu lintasan dengan get(kunci, 0) + 1 atau Counter, berbiaya $O(n)$ waktu dan $O(k)$ ruang.
• Anagram terdeteksi dengan membandingkan dua peta atau satu peta yang dinaikkan lalu diturunkan hingga nol.
• Kunci kanonik dari huruf terurut mengelompokkan anagram, dan mayoritas ditemukan dari frekuensi yang melampaui setengah banyaknya data.
• HashMap Java menuliskan pola yang sama dengan merge dan penyapuan entrySet.

Referensi#

• collections — Python Software Foundation — dokumentasi Counter beserta most_common untuk peta frekuensi.
• HashMap — Oracle — dokumentasi merge dan operasi HashMap lain yang dipakai pada demo Java.
• Anagram — Wikipedia — definisi anagram beserta contohnya.
• Algorithms, 4th Edition — Princeton University — materi tabel simbol berbasis hash yang menaungi pola penghitungan.