David Albert Huffman

En iyi fikir, bazen çöpe attığınız notların arasında saklıdır.

David Albert Huffman, Amerikalı mühendistir. 20. yüzyılın ikinci yarısında bilgi teorisi, veri sıkıştırma ve dijital devre tasarımı alanlarında çığır açtı.

1925'te Alliance'ta doğdu. Genç yaşta matematiğe olan ilgisiyle dikkat çekti. Lisede calculus derslerini kendi kendine çalışarak öğrendi. 1944 yılında henüz 18 yaşında Ohio Eyalet Üniversitesi'nden Elektrik Mühendisliği lisans derecesini birincilikle aldı. II. Dünya Savaşı sırasında ABD Donanması’nda radar teknisyeni olarak görev yaptı; bu deneyim, sinyal işleme ve iletişim sistemlerine ilgisini pekiştirdi. Savaş sonrası Massachusetts Institute of Technology (MIT)’ye kabul edildi. 1949’da yüksek lisansını tamamladı.

1953 yılında MIT'den doktora derecesini aldı. Huffman Kodlaması, aslında tam da bu doktora çalışması sırasında ortaya çıktı. 1952’de geliştirdiği Huffman Kodlaması ile tanınır; bu algoritma, kayıpsız veri sıkıştırmasının evrensel standardı haline gelmiş, ZIP, JPEG, PNG, MP3 ve modern arşivleme sistemlerinin temel yapı taşlarından biri olmuştur. Doktora danışmanı, bilgi teorisinin babası Claude E. Shannon’ın yakın çalışma arkadaşı Robert M. Fano’ydu. Profesörü, Huffman’a dönemin en zor açık problemlerinden birini vermişti: “Verilen sembol frekanslarına göre, kayıpsız sıkıştırma için en kısa ortalama kod uzunluğunu sağlayan ikili kod nasıl tasarlanır?” Bu problem, Shannon-Fano kodlamasının sınırlarını zorluyordu. Huffman Kodlaması'nın ortaya çıkışı, bilim tarihinde sık rastlanan "problem çözme azmi" hikayelerinden biridir. Huffman, kodlama problemini çözmek için haftalarca uğraşmış ve tatmin edici bir çözüm bulamamıştı. Klasik yaklaşımlarla, kökten yapraklara metoduyla uğraşmıştı. Hatta tezi bırakıp başka bir konuya geçmeyi bile düşünüyordu. Bu karamsar anlardan birinde, tezin notlarını çöpe atarken son bir kez gözden geçirdi. İşte o anda tersine bir fikir doğdu: “Ya eğer ağacı yapraklardan, en sık sembollerden köke doğru birleştirirsem ne olur?” Bugün bilinen açgözlü algoritma fikri parlamıştı. Bu açgözlü strateji, her adımda en düşük frekanslı iki düğümü birleştirerek ilerledi. Huffman'ın çözümü sadece bir yöntem değildi; kanıtlanabilir şekilde optimumdu. Karakterlerin frekansları bilindiğinde, kayıpsız sıkıştırma için mümkün olan en kısa toplam bit dizisini üretiyordu: Huffman Kodu = Minimum redundancy code = Entropiye en yakın kod. Buluş, greedy algoritmaların küresel optimum üretebileceğinin ilk güçlü kanıtlarından biri oldu. 1952’de yayımlanan makalesi (“A Method for the Construction of Minimum-Redundancy Codes”, Proceedings of the IRE), bilgi teorisi literatürünün klasiklerinden biri kabul edilir.

Doktorasının ardından MIT'de çalıştıktan sonra, kariyerinin büyük bir bölümünü, 1967'den 1994'e kadar profesör ve bölüm başkanı olarak görev yaptığı Santa Cruz'daki Kaliforniya Üniversitesi'nde (UCSC) geçirdi. UCSC'nin Bilgisayar Mühendisliği Bölümü'nün kurulmasında öncü rol oynadı. UCSC’nin ilk bilgisayar laboratuvarını kurdu. Bölümü, donanım-yazılım entegrasyonunda öncü bir merkez haline getirdi. Sadece bir dahi değil, aynı zamanda müthiş bir öğretmendi. Öğrencilerine karşı sabırlı, destekleyici ve ilham verici kişiliğiyle tanınırdı. Karmaşık konuları basit benzetmelerle anlatmasıyla ünlüydü.

Bilgisayar donanımının temelini oluşturan sıralı devrelerin (sequential circuits) tasarımında da önemli teorik çalışmalar yaptı. "Minimal Kapalı Durum Makineleri" üzerine yaptığı çalışmalar, bilgisayar bilimi ve dijital devre tasarımının kuramsal temellerini attı.

1998'de “Veri sıkıştırma ve sıralı devre teorisine temel katkıları” dolayısıyla IEEE Richard W. Hamming Madalyası aldı. Bilgi teorisi alanındaki en saygın ödüllerden biri olan Claude E. Shannon Ödülü'nü kazandı. Claude E. Shannon Ödülü bilgi teorisinin Nobel’i sayılır. Şöhretine rağmen “Ben sadece bir problem çözdüm” diyordu.

1999'da Santa Cruz'da öldü.

Huffman Kodlaması, modern bilgisayar dünyasının temel taşlarından biridir. Geliştirildiği 1952 yılından bu yana, 70 yılı aşkın bir süredir neredeyse tüm kayıpsız veri sıkıştırma formatlarının bir parçasıdır. Huffman Kodlaması, teorik bilgisayar biliminin pratik uygulamadaki başarısının en güzel örneklerinden biridir. Algoritmanın basitliği, zarafeti ve optimum sonuç vermesi, onu üniversitelerin Bilgisayar Bilimleri derslerinde veri yapıları ve algoritmalar konusunun standart bir parçası yapmıştır. Bu algoritma, Açgözlü Algoritmalar (Greedy Algorithms) olarak bilinen bir algoritma sınıfının klasik bir örneğidir. Açgözlü algoritmalar, her adımda o anki en iyi seçeneği seçerek ilerler ve Huffman'ın durumunda bu yerel en iyi seçimler, şaşırtıcı bir şekilde küresel optimum sonucu doğurur. David A. Huffman, bir doktora teziyle bir endüstrinin çehresini değiştirdi. Sade ve zarif bir keşfin sahibi olarak bilim dünyasında ölümsüzleşti.

Kitap olarak yayınlanmış bir çalışması bulunmamaktadır. Makaleleri: A Method for the Construction of Minimum-Redundancy Codes (1952), The Synthesis Problem of Sequential Switching Circuits (1953), The Synthesis of Sequential Switching Circuits (1954), Canonical Feedback Expressions for Sequential Machines (1963), Impossible Objects as Nonsense Sentences (1975), The Interpretation of Visual Illusions (1976), Curved Creases and Crease Patterns (1976), Impossible Objects: Computational Studies (1981), A Mathematical Theory of Paper Folding (1985), Kaleidocycles (1988).