Functional Testing

 Selama pembuatan perangkat lunak tentunya kita sering menemukan bug atau error. Sehingga, untuk mengurangi atau menghindari banyaknya bug maka diperlukan pengujian perangkat lunak/software testing. Software testing adalah cara menilai produk perangkat lunak untuk membedakan antara informasi yang diberikan dan hasil yang diharapkan. Selain itu, untuk mengevaluasi karakteristik suatu produk. Pada dasarnya software testing penting dilakukan untuk menjaga kualitas perangkat lunak tersebut. Tetapi, apakah kalian sudah mengetahui jenis-jenis software testing?

Jenis-jenis software testing tergantung pada berbagai faktor seperti project requirements, anggaran, timeline, keahlian, dan kesesuaian. Terdapat dua jenis pengujian yang dilakukan oleh QA atau Software Tester yaitu functional testing dan non-functional testing. Pada artikel ini akan dibahas tentang jenis-jenis software testing pada functional testing.

Functional Testing adalah jenis pengujian yang memverifikasi bahwa setiap fungsi aplikasi telah beroperasi sesuai dengan requirement specification. Functional testing berfokus pada manual dan automation testing.

Jenis-jenis functional testing, antara lain :

• Unit Testing
• Integration Testing
• System Testing
• Interface Testing
• Regression Testing
• User Acceptance Testing

Unit Testing

Unit testing adalah salah satu tingkat dari software testing di mana masing-masing unit/komponen perangkat lunak diuji. Tujuannya adalah untuk memvalidasi bahwa setiap unit perangkat lunak telah berfungsi sesuai dengan rancangannya. Unit adalah bagian terkecil yang dapat diuji dari perangkat lunak. Biasanya mempunyai satu atau beberapa input dan biasanya mempunyai satu output.

Integration Testing

Integration testing adalah salah satu tingkat dari software testing di mana masing-masing unit digabungkan dan diuji sebagai kelompok. Tujuan dari tingkat pengujian ini adalah untuk mengekspos kesalahan dalam interaksi antara unit yang terintegrasi.

Terdapat beberapa pendekatan dalam integration testing, antara lain :

• Big Bang → Semua atau sebagian besar unit digabungkan dan diuji sekaligus. Pendekatan ini diambil ketika tim tester menerima seluruh perangkat lunak dalam satu bundel.
• Top Down → Unit tingkat atas diuji terlebih dahulu.
• Bottom Up → Unit level bawah diuji terlebih dahulu.
• Sandwich / Hybrid → Kombinasi dari pendekatan Top Down dan Bottom Up.

System Testing

System testing adalah salah satu tingkat dari software testing di mana perangkat lunak yang lengkap dan terintegrasi diuji. Tujuan dari pengujian ini adalah untuk mengevaluasi kepatuhan sistem dengan persyaratan yang ditentukan.

Task yang dilakukan dengan menggunakan system testing, yaitu :

• System Test Plan → Prepare, Review, Rework, Baseline
• System Test Cases → Prepare, Review, Rework, Baseline
• System Test → Perform

Interface Testing

Ketika aplikasi dikembangkan, maka ada beberapa komponen seperti server, database, dll. Koneksi yang mengintegrasikan dan memfasilitasi komunikasi antara komponen-komponen ini disebut sebagai Interface. Fungsi dari interface adalah memverifikasi bahwa komunikasi antara sistem dilakukan dengan benar.

Berikut ini tiga fase dalam interface testing :

• Configuration & development → Ketika interface dikonfigurasi, dan begitu pengembangan dimulai, konfigurasi perlu diverifikasi sesuai kebutuhan.
• Validation → Ketika pengembangan selesai, interface perlu divalidasi dan diverifikasi, ini dapat dilakukan sebagai bagian dari pengujian unit juga.
• Maintenance → Ketika kita mulai mengembangkan interface, kita perlu memastikan bahwa tidak ada bug apapun dalam kode yang dibuat sehingga diperlukan sebuah pengujian yang harus dijalankan pada interface.

Regression Testing

Regression testing adalah tahap penting & sangat berguna bagi pengembang untuk mengidentifikasi stabilitas produk dengan perubahan requirements. Regression testing adalah pengujian yang dilakukan untuk memverifikasi bahwa perubahan kode pada perangkat lunak tidak memengaruhi fungsionalitas produk yang ada.

Terdapat beberapa teknik dalam regression testing, antara lain :

• Retest all → Seluruh test case di test suite dieksekusi kembali untuk memastikan bahwa tidak ada bug yang terjadi karena perubahan kode.
• Regression Test Selection → Dalam metode ini, test case dipilih dari test suite untuk dieksekusi kembali. Tidak seluruh suite dieksekusi ulang. Pemilihan test case dilakukan atas dasar perubahan kode dalam modul.
• Test Case Prioritization → Test case dengan prioritas tinggi dieksekusi terlebih dahulu daripada prioritas menengah dan rendah. Prioritas test case tergantung pada kekritisan dan dampaknya pada produk.
• Hybrid → Teknik hybrid adalah kombinasi dari pemilihan regression testing dan priotitas test case. Teknik ini memilih test case yang dieksekusi kembali dengan bergantung pada prioritasnya.

User Acceptance Testing

Acceptance testing adalah salah satu tingkat dari software testing di mana suatu sistem diuji untuk dapat diterima. Tujuan dari pengujian ini adalah untuk mengevaluasi kesesuaian sistem dengan business requirements dan menilai apakah sudah layak untuk delivery.

Terdapat beberapa jenis user acceptance testing, antara lain :

• Business Acceptance Testing (BAT) → Ini untuk menilai apakah produk memenuhi tujuan bisnis atau tidak. Ini terutama berfokus pada manfaat bisnis karena kemungkinan kondisi pasar yang dapat berubah.
• Contract Acceptance Testing (CAT) → Ini adalah kontrak yang menentukan bahwa setelah produk ditayangkan, dalam periode yang telah ditentukan, accepteance test harus dilakukan dan harus melewati semua acceptance use cases.
• Operational Acceptance Testing (OAT) → Ini untuk menilai kesiapan operasional produk dan merupakan pengujian non-fungsional. Ini terutama mencakup pengujian-pengujian seperti recovery, compatibility, maintainability, technical support availability, reliability, fail-over, localization, dll.
• Alpha Testing → Ini untuk menilai produk dalam lingkungan pengembangan/pengujian oleh tim tester khusus yang biasa disebut alpha tester.
• Beta Testing → Ini untuk menilai produk dengan menunjukkan kepada end-user yang sebenarnya, biasanya disebut beta testers/beta users, di lingkungan mereka. Umpan balik terus menerus dari pengguna dikumpulkan dan dilakukan perbaikan.
  
  

resource : medium

SOFTWARE TESTING METODOLOGI

 Pengujian perangkat lunak merupakan bagian integral dari software development life cycle (SDLC). Secara efektif dan efisien pengujian sebaris kode yang sama pentingnya, dengan  penulisanya . Jadi apa pentingnya  pengujian software ini?, bagi Anda  yang sering mencari  freeware legal yang  gratis dari pengembang software ternama, secara tidak sadar anda telah menjadi seorang software tester untuk pengujian, walaupun  kita sering  mendapatkan masalah error saat menjalankan di semua versi windows, yang secara otomatis merecord kondisi error dan akan selalu menampilkan pesan kesalahan  yang link lansung ke microsoft sebagai perbaikan untuk bug mereka yang selanjutnya akan  diterbitkan sebagai update pada versinya.

Software yang di uji  tidak lain hanyalah menundukkan sebaris  kode untuk keduanya,
dikontrol serta kondisi operasi yang tidak terkendali, dalam upaya untuk
mengamati output dan memeriksa apakah sesuai dengan beberapa pra-syarat-syarat
tertentu. Set tes yang berbeda kasus dan strategi pengujian siap, yang semuanya
bertujuan untuk mencapai satu tujuan yang sama – menghilangkan semua bug dan
error dari kode dan membuat software bebas kesalahan dan cukup mampu
memberikan output yang akurat dan optimal.

Ada beberapateknik dalam pengujian software  dan metodologi pengujian. Metodologi pengujian software berbeda dari teknik pengujian software . Kita akan melihat beberapa metodologipengujian perangkat lunak di bagian akhir artikel ini.

Methods Testing Software
Ada berbagai jenis metode atau teknik pengujian sebagai bagian dari proses pengujian software. Saya telah mencari beberapa refrensi di beberapa web seperti dibawah ini

• White box testing
• Black box testing
• Gray box testing
• Unit testing
• Integration testing
• Regression testing
• Usability testing
• Performance testing
• Scalability testing
• Software stress testing
• Recovery testing
• Security testing
• Conformance testing
• Smoke testing
• Compatibility testing
• System testing
• Alpha testing
• Beta testing

metode  Di atas pengujian sofware  dapat diimplementasikan dalam dua cara – secara manual atau dengan otomatisasi. Manual software testing dilakukan  oleh penguji software yang secara fisik  yaitu memeriksa dengan cara manual, menguji dan melaporkan kesalahan atau bug dalam produk atau potongan kode. Dalam kasus software testing otomatis, proses yang samadilakukan oleh komputer melalui suatu pengujian otomatis software seperti WinRunner, LoadRunner, Test Director, dll

Software Testing Metodologi
beberapa  software yang umum digunakan dalam metodologi pengujian:

• Waterfall model
• V model
• Spiral model
• RUP
• Agile model
• RAD

Waterfall Model

Model Waterfall (air terjun) mengadopsi ‘top down’ pendekatan terlepas dari apakah itu digunakan untuk pengembangan perangkat lunak atau pengujian. Langkah-langkah dasar yang terlibat dalam metodologi pengujian perangkat lunak ini adalah:
1. Kebutuhan analisis
2.Kasus uji desain
3.Ujian pelaksanaan
4. Pengujian, debugging dan mengesahkan kode atau produk
5.Penyebaran dan pemeliharaan

Dalam metodologi ini, Anda melanjutkan ke langkah berikutnya hanya setelah Anda menyelesaikan langkah ini. Ada peluang untuk melompat mundur atau maju atau melakukan dua langkah secara bersamaan. Selain itu, model ini mengikuti pendekatan non-iteratif. Manfaat utama dari metodologi ini adalah sederhana, sistematis dan pendekatan ortodoks. Namun, memiliki banyak kelemahan karena bug dan kesalahan dalam kode tidak ditemukan sampai dan kecuali tahap pengujian tercapai. Ini dapat sering mengakibatkan pemborosan waktu, uang dan sumber daya berharga.

V Model

model V mendapatkan namanya dari fakta bahwa representasi grafis dari aktivitas proses pengujian berbeda terlibat dalam metodologi ini mirip dengan huruf ‘V’. Langkah-langkah dasar yang terlibat dalam metodologi ini kurang lebih sama dengan yang di model air terjun. Namun, kedua model ini mengikuti ‘top-down’ maupun ‘bottom-up’ pendekatan (Anda dapat membayangkan mereka membentuk huruf ‘V’). Keuntungan metodologi ini adalah bahwa dalam kasus ini, baik perkembangan dan kegiatan pengujian . Sebagai contoh, sebagai tim pengembangan terjadi tentang kegiatan analisis kebutuhan, tim pengujian secara simultan dimulai dengan kegiatan pengujian penerimaan. Dengan mengikuti pendekatan ini, waktu penundaan diminimalkan dan optimal pemanfaatan sumber daya terjamin.

Spiral Model

Seperti namanya, model spiral mengikuti suatu pendekatan di mana terdapat sejumlah siklus (atau spiral) dari semua langkah-langkah berurutan seperti pada  Waterfall Model. Begitu siklus awal selesai, sebuah analisis mendalam dan review dari produk atau output yang dicapai dilakukan. Jika tidak sesuai persyaratan yang ditentukan atau diharapkan standar, mengikuti siklus kedua, dan seterusnya. Metodologi ini mengikuti pendekatan berulang-ulang dan umumnya cocok untuk proyek-proyek besar yang kompleks dan terus-menerus mengalami perubahan persyaratan.

Rational Unified Process (RUP)

RUP metodologi yang juga mirip dengan model spiral dalam arti bahwa seluruh prosedur pengujian ini dipecah menjadi beberapa siklus atau proses. Setiap siklus terdiri dari empat tahap yaitu; awal, elaborasi, konstruksi dan transisi. Pada akhir setiap siklus, produk atau output ditinjau dan siklus selanjutnya (terdiri atas empat fase yang sama) berikut jika diperlukan. Hari ini, Anda akan menemukan organisasi dan perusahaan tertentu yang sedikit mengadopsi versi modifikasi dari RUP, yang pergi dengan nama Enterprise Unified Process (eup).

Agile Model

Metodologi ini tidak mengikuti pendekatan sekuensial yang murni dan juga tidak mengikuti pendekatan iteratif yang murni. Ini adalah campuran selektif kedua pendekatan di samping beberapa metode pengembangan baru. Cepat dan pengembangan tambahan merupakan salah satu prinsip-prinsip kunci dari metodologi ini. Fokusnya adalah pada mendapatkan hasil cepat, praktis dan terlihat keluaran dan hasil, daripada hanya mengikuti proses teoritis. interaksi berkelanjutan dari  pelanggan dan partisipasi merupakan bagian integral dari seluruh proses pengembangan.

Rapid Application Development (RAD)

Dalam kasus ini, metodologi yang mengadopsi pendekatan pembangunan yang cepat dengan menggunakan prinsip konstruksi berbasis komponen. Setelah memahami berbagai persyaratan, prototipe yang cepat telah disiapkan dan kemudian dibandingkan dengan serangkaian output diharapkan kondisi dan standar. Diperlukan perubahan dan modifikasi yang dibuat setelah diskusi bersama dengan pelanggan atau tim pengembangan (dalam konteks pengujian perangkat lunak). Meskipun pendekatan ini memang memiliki pangsa keuntungan, dapat cocok jika proyek besar, kompleks dan kebetulan dari alam yang sangat dinamis, di mana persyaratan selalu berubah.

Ini adalah gambaran singkat dari beberapa pengujian perangkat lunak yang umum digunakan metodologi. Dengan aplikasi teknologi informasi yang tumbuh dari hari ke hari, pentingnya pengujian perangkat lunak yang tepat telah tumbuh multifold.

resource:inconcept

Mengenal STLC — Software Testing Life Cycle

Software Testing Life Cycle (STLC) adalah tahap-tahap proses pengujian yang dilaksanakan secara sistematis dan terencana. Dalam proses STLC, berbagai kegiatan dilakukan untuk meningkatkan kualitas produk. Meskipun SDLC dan STLC terkesan mirip, namun penerapannya berbeda. SDLC diterapkan pada semua tahap pengembangan software, sedangkan STLC hanya terbatas pada tahap pengujian software.

STLC mengacu pada tahap-tahap yang spesifik dalam proses pengujian untuk memastikan kualitas produk. Setiap tahap-tahap dari STLC memiliki Entry Criteria , Exit Criteria , Activities dan Deliverable yang terkait.

Lalu apa itu Entry Criteria dan Exit Criteria ?

• Entry Criteria adalah ketentuan yang harus kita penuhi sebelum pengujian dapat dimulai.
• Exit Criteria mendefinisikan ketentuan yang harus diselesaikan sebelum menyelesaikan pengujian.
• Activities adalah kegiatan-kegiatan yang diprelukan untuk melakukan pengujian.
• Deliverable adalah hasil yang didapatkan setelah kita menyelesaikan pengujian.

1. Requirement Analysis

Requirement analysis adalah tahap pertama dalam software testing life cycle atau STLC. Requirement software yang sudah ada dari stakeholder (system analyst, product manager, etc) kemudian dianalisa oleh tim QA untuk mengetahui detail software, module, fitur dan fungsi yang akan dibangun, review dan melakukan validasi jika masih ada kekurangan dan atau untuk melengkapi kejelasan requirement tersebut, menganalisa apa saja yang dapat diuji (testable) secara manual dan automated serta menganalisa cakupan fungsi atau fitur mana saja yang akan diuji secara functional dan non-functional.

2. Test Planning

Tahap planning adalah tahap kedua dari proses STLC yang juga dapat disebut dengan test planning atau test strategy. Pada tahap ini tim QA mempersiapkan rencana untuk melakukan pengujian berdasarkan requirement analysis. Pada tahap ini akan ditentukan tools yang akan digunakan untuk menguji dan hal hal yang di deliver setelah pengujian, estimasi waktu dan sumber daya , pembagian peran serta tanggung jawab pada tim QA.

3. Test Case Development

Pada tahap selanjutnya adalah development. Tahap ini berisi hal-hal yang akan menjadi acuan dalam pengujian yang melibatkan untuk membuat test case, membuat test data, membuat script automation test berdasarkan test case.

Test Case adalah sekumpulan skenario yang disusun oleh QA agar sistem yang akan dites dapat memenuhi ketentuan, standar tertentu serta dapat berfungsi dengan baik.

4. Test Environment Setup

Pada tahap ini proses yang dilakukan adalah memastikan environment test dapat berjalan dengan baik dan sesuai harapan. Pada dasarnya environment test menentukan syarat software yang diujian mulai melakukan smoke test untuk memastikan environment test apakah sudah benar-benar siap.

Smoke test adalah testing yang dilakukan untuk memastikan fitur atau fungsi penting dari suatu program berjalan dengan baik sebelum dilakukannya tes fungsional atau regression.

5. Test Execution

Tahap selanjutnya yaitu test execution, setelah software siap uji dan persiapan pengujian siap. Pada tahap ini pengujian dilakukan berdasarkan test plan dan test case yang disepakati di tahap sebelumnya. Fitur yang berjalan sesuai dengan test requirement, status fitur tersebut adalah pass atau berhasil, dan siap untuk masuk ke tahap deployment. Jika fungsi tidak berjalan sesuai dengan requirement, maka tergantung dari kategori error atau bug yang terjadi. Error yang ditemukan tersebut dimasukkan ke dalam test report tim QA untuk disampaikan ke tim developer untuk diperbaiki, dan kembali diuji oleh tim QA. Pada tahap ini juga dilakukan sanity testing dan regression testing ketika akan melakukan deployment program.

6. Test Cycle Closure

Pada tahap akhir dilakukan meeting anggota tim untuk mengidentifikasi dan menganalisis rencana yang akan dilakukan di masa depan dan evaluasi terhadap STLC yang dijalankan saat ini. Tujuannya adalah untuk meminimalkan hambatan saat proses pengujian dan meningkatkan kualitas dalam menjalankan STLC di masa depan.

sumber: medium 

 

Dynamic Programming

Dynamic Programming (selanjutnya disebut “DP” saja) merupakan salah satu teknik perancangan algoritma yang dikembangkan untuk menyelesaikan permasalahan yang sangat kompleks dengan memecah permasalahan tersebut menjadi banyak sub-permasalahan. Perbedaan utama DP dengan Divide and Conquer (selanjutnya disebut “D&C”) adalah pada DP kita menggunakan kembali hasil kalkulasi sub-masalah yang telah dilakukan sebelumnya. Apa artinya?

Untuk mempermudah penjelasan, mari kita selesaikan masalah sederhana yang telah kita bahas berkali-kali: perhitungan bilangan fibonacci. Algoritma untuk menyelesaikan perhitungan fibonacci secara naif adalah seperti berikut:

def fibonacci(n):
    if n <= 2:
        hasil = 1
    else:
        hasil = fibonacci(n - 1) + fibonacci(n - 2)

    return hasil

Algoritma fibonacci sederhana seperti di atas dapat dikatakan sebagai algoritma D&C, karena kita membagikan perhitungan fibonacci ke dua fungsi fibonacci, sampai didapatkan nilai hasil terkecilnya. Pemanggilan fungsi fibonacci di atas dapat digambarkan seperti berikut:

Pemanggilan Fungsi Fibonacci

Perhatikan bagaimana f(n−2)$f(n-2)$ dan f(n−3)$f(n-3)$ dikalkulasikan sebanyak dua kali, dan semakin kita masuk ke dalam pohon pemanggilan, kita akan melihat semakin banyak fungsi-fungsi yang dipanggil berkali-kali. Pendekatan DP menghindari kalkulasi fungsi yang berulang kali seperti ini dengan melakukan memoization, yaitu menyimpan hasil kalkulasi fungsi tersebut dan menggunakan nilai yang disimpan ketika perhitungan yang sama dibutuhkan kembali. Dengan menyimpan hasil kalkulasi seperti ini, tentunya jumlah total langkah perhitungan yang harus dilakukan menjadi berkurang.

Misalnya, kita dapat menyimpan hasil kalkulasi dari fungsi fibonacci tersebut pada sebuah dictionary, seperti berikut:

memo = dict()

def fibonacci_dp(n):
    if n in memo.keys():
        return memo[n]
    elif n <= 2:
        hasil = 1
    else:
        hasil = fibonacci_dp(n - 1) + fibonacci_dp(n - 2)
    memo[n] = hasil
    return hasil

Dengan menyimpan hasil kalkulasi dari fungsi yang telah ada, maka proses pemanggilan fungsi akan menjadi seperti berikut:

Pemanggilan Fungsi Fibonacci Dynamic Programming

Seperti yang dapat dilihat, pohon pemanggilan fungsi terpotong setengahnya! Tentunya perhitungan fibonacci akan menjadi sangat efisien dengan menggunakan fungsi yang baru ini.

Pendekatan lain dalam menghitung fibonacci lagi, yang masih adalah DP, yaitu dengan menghitung nilai fibonacci dari bawah pohon (pada kode sebelumnya kita melakukan perhitungan dari atas pohon):

def fibonacci_dp_bu(n):
   memo = dict()
   for i in range(1, n + 1):
       if i <= 2:
           hasil = 1
       else:
           hasil = memo[i - 1] + memo[i - 2]
       memo[i] = hasil
   return memo[n]

Untuk melihat efek langsung dari ketiga fungsi tersebut, coba jalankan ketiga fungsi tersebut untuk n yang sama, dan lihat perbedaan waktu eksekusinya! Sebagai latihan tambahan, hitung juga kompleksitas dari ketiga fungsi perhitungan fibonacci tersebut.

Mari kita rangkum hal yang telah kita pelajari mengenai DP sejauh ini:

1. DP menyelesaikan masalah dengan memecah masalah menjadi sub-permasalahan.
2. Setiap solusi dari sub-permasalahan yang telah didapatkan disimpan untuk digunakan kembali jika terdapat sub-permasalahan yang sama. Teknik ini dikenal dengan nama memoization.
3. DP tidak harus menggunakan rekursif. Pemecahan sub-permasalahan juga dapat dilakukan dengan iterasi maupun kalkulasi sederhana.

Contoh Aplikasi Dynamic Programming: Text Justification

Kegunaan utama dari DP adalah untuk menyelesaikan masalah optimasi. Permasalahan optimasi artinya permasalahan yang mencari nilai terbaik, baik maksimal maupun minimal, dari sebuah solusi. Salah satu contoh paling praktis dalam penerapan DP model ini adalah algoritma untuk membuat teks rata tengah. Bagaimana cara kerja algoritma ini? Mari kita lihat masalah yang ingin diselesaikan terlebih dahulu.

Pada aplikasi pengolah kata seperti Microsoft Word, biasanya terdapat fitur untuk menentukan kemerataan teks yang ada pada paragraf, seperti yang nampak pada gambar di bawah:

Fitur Pemerataan Teks pada Microsoft Word

Bagaimana kita menentukan kemerataan teks? Secara umum, kemerataan sebuah teks ditentukan oleh beberapa hal berikut:

1. Ukuran dari halaman, yang tentunya akan mempengaruhi berapa lebar maksimal dari sebuah teks.
2. Ukuran setiap kata yang ada dalam teks, untuk menghitung berapa banyak kata yang dapat dimasukkan ke dalam satu baris teks.
3. Ukuran spasi dalam teks, seperti ukuran kata, untuk menghitung jumlah kata yang dapat dimasukkan ke dalam teks.
4. Ukuran karakter-karakter khusus seperti ”!”, ”?”, ”,”,”.”, dan lainnya. Meskipun biasanya berukuran kecil, karakter khusus tetap berperan dalam mengisi ruang tulisan.

Dengan melakukan kalkulasi sederhana dari teks, tentunya kita bisa saja melakukan pemerataan teks dengan mudah. Misalnya, untuk menghitung total teks yang dapat masuk ke dalam sebuah baris tulisan, kita dapat menggunakan persamaan berikut:

ukuran halaman←total ukuran kata+total ukuran spasi+total ukuran simbol$$\text{ukuran halaman}\leftarrow \text{total ukuran kata}+\text{total ukuran spasi}+\text{total ukuran simbol}$$

Sehingga untuk membuat sebuah teks menjadi rata penuh (justified) kita dapat memasukkan setiap kata, spasi, dan simbol satu demi satu sampai kita memenuhi sebuah baris. Jika kata selanjutnya tidak lagi memiliki ukuran yang cukup, maka kita dapat menambahkan spasi di tengah-tengah kata sebelumnya sampai baris penuh, dan lalu berpindah baris.

Secara sederhana, algoritma naif untuk melakukan rata penuh teks adalah seperti berikut:

1. Ambil satu elemen dalam teks, baik berupa kata, simbol, maupun spasi. Masukkan elemen ini ke dalam baris.

2. Hitung ukuran baris sekarang.

3. Ambil satu elemen lagi dalam teks, dan hitung ukurannya.

4. Tambahkan ukuran baris sekarang dengan ukuran elemen berikutnya. Hasil pengukuran ini selanjutnya akan disebut “Ukuran Baris Selanjutnya” atau UBS.

5. Cek nilai UBS:

   1. Jika UBS masih lebih kecil dari lebar halaman, kembali ke langkah 1

   2. Jika UBS sudah lebih dari lebar halaman:

      1. Tambahkan spasi di antara setiap kata dalam baris sampai ukuran baris sama dengan lebar halaman.

Secara kasar, algoritma di atas dapat diimplementasikan seperti kode berikut (yang jelas tidak dapat dijalankan):

def naive_justify(text, page_size):
    next = text.get_next()
    total_size = 0
    next_total_size = total_size + next.size()

    lines = [[next]]
    current_line = 0

    while(!text.empty()):
        while(next_total_size < page_size):
            total_size = next_total_size
            next = text.get_next()
            lines[current_line].push(next)
            next_total_size = total_size + next.size()

        while total_size != page_size:
            add_space(lines[current_line])

        current_line = current_line + 1

Hasil algoritma di atas kurang optimal, karena ketika terdapat kata-kata yang panjang dalam sebuah kalimat, kita terpaksa harus memotong baris terlalu cepat, dan akhirnya menambahkan banyak spasi. Contoh eksekusi dari algoritma di atas dapat dilihat pada gambar berikut:

Hasil Algoritma Pemerataan Teks Sederhana

Perhatikan bagaimana teks “Dynamic Programming”, “dikembangkan untuk”, dan “memecah permasalahan” memiliki spasi yang sangat lebar. Menggunakan DP, kita dapat menghasilkan pemerataan teks yang lebih optimal.

Berdasarkan algoritma sebelumnya yang kita kembangkan, dapat dilihat bagaimana optimasi dari rata penuh sebuah teks terdapat pada kapan kita melakukan pergantian baris. Jika kita mengganti baris terlalu cepat (jumlah kata masih sedikit), maka secara otomatis kita harus menambahkan banyak spasi, yang menyebabkan teks tidak enak dilihat. Untuk mendapatkan jumlah kata yang optimal dalam sebuah baris, kita akan melakukan perhitungan tingkat “keburukan” sebuah kata dalam teks, jika kata tersebut dijadikan pengganti baris. Kita kemudian dapat mencari tingkat keburukan setiap kata yang ada dalam teks, dan mengambil kata yang memiliki tingkat keburukan terendah sebagai tanda berganti baris.

Pengukuran tingkat keburukan teks sendiri tentunya ditentukan oleh jumlah ruang kosong yang ada dari teks sampai ke ujung halaman. Misalnya, pada gambar di bawah kita dapat melihat contoh ruang kosong dari teks sampai ke ujung halaman:

Tingkat Keburukan Teks

Pada gambar di atas, blok berwarna merah berarti tingkat keburukannya tinggi, dan blok berwarna hijau berarti tingkat kebukurannya rendah. Untuk mendapatkan nilai keburukan yang paling kecil dalam sebuah teks, tentunya kita harus menghitung seluruh kombinasi nilai keburukan dari elemen-elemen yang ada dalam teks. Perhitungan kombinasi nilai keburukan ini tentunya merupakan masalah yang tepat untuk algoritma DP, karena setiap perhitungan nilai keburukan pada dasarnya adalah sebuah sub-masalah!

Jadi sekarang kita telah menemukan sub-masalahnya: mencari nilai keburukan dari sebuah elemen. Bagaimanakah kita dapat menggunakan teknik DP untuk menyelesaikan masalah ini? Ketika menghitung kombinasi dari nilai keburukan dari setiap elemen, secara tidak langsung kita akan membangun sebuah Directed Acyclic Graph, seperti yang tampak pada gambar berikut:

DAG dalam Teks

dengan setiap k$k$ merepresentasikan tingkat keburukan dari elemen tersebut. Menggunakan informasi tersebut, kita dapat mencari nilai minimal dari total seluruh nilai keburukan yang ada pada sebuah teks untuk mendapatkan titik penggantian baris yang paling tepat. Untuk merangkum, berikut adalah langkah-langkah untuk algoritma yang sedang kita kembangkan:

1. Ambil setiap elemen dari dalam teks.
2. Untuk setiap elemen yang ada, lakukan: 1. Hitung nilai keburukan dari elemen terhadap elemen-elemen lain dalam teks. 2. Hitung total nilai keburukan yang ada pada elemen yang sedang dicari.
3. Tentukan nilai keburukan minimum dari nilai keburukan seluruh elemen yang telah dihitung pada langkah 2.
4. Ambil elemen yang memiliki nilai keburukan minimum.
5. Ganti baris pada elemen dengan nilai keburukan minimum.

Perhitungan nilai keburukan sendiri dapat dilakukan dengan menggunakan rumus sederhana berikut:

keburukan(i,j)={ukuran baris>lebar halaman(lebar halaman−ukuran baris)3∞$$\begin{array}{r}keburukan(i,j)=\{\begin{array}{ll}\text{ukuran baris}>\text{lebar halaman}& \mathrm{\infty }\\ (\text{lebar halaman}-\text{ukuran baris}{)}^3\end{array}\end{array}$$

dengan i$i$ dan j$j$ sebagai awal dan akhir dari kata yang ingin dihitung tingkat keburukannya. Jika dijadikan kode program, algoritma tersebut dapat dituliskan seperti berikut:

def length(word_lengths, i, j):
    return sum(word_lengths[i- 1:j]) + j - i + 1


def break_line(text, L):
    # wl = lengths of words
    wl = [len(word) for word in text.split()]

    # n = number of words in the text
    n = len(wl)

    # total badness of a text l1 ... li
    m = dict()
    m[0] = 0

    s = dict()

    for i in range(1, n + 1):
        sums = dict()
        k = i
        while (length(wl, k, i) <= L and k > 0):
            # badness calculation
            sums[(L - length(wl, k, i))**3 + m[k - 1]] = k
            k -= 1
        m[i] = min(sums)
        s[i] = sums[min(sums)]

    return s

Perlu dicatat bahwa kode di atas belum mengikut sertakan spasi dalam perhitungan, dan juga belum membangun kembali baris-baris yang telah dipecah menjadi sebuah teks (paragraf).

Kesimpulan

Secara sederhana, teknik DP dapat dikatakan adalah sebuah teknik brute force yang pintar. Kita memecah-mecah masalah menjadi sub-masalah, dan menyelesaikan seluruh sub-masalah tersebut. Perbedaan utama dari DP dengan D&C adalah DP melakukan penyimpanan hasil penyelesaian sub-masalah sehingga kita tidak perlu menyelesaikan sub-masalah yang sama berulang kali.

source: http://dev.bertzzie.com/