Co łączy wyszukiwarki internetowe, bazy danych i książki telefoniczne? Przede wszystkim cel – ich zadaniem jest przechowywanie informacji i umożliwienie użytkownikom szybkiego dostępu do nich. Wbrew pozorom podobna jest też implementacja. Mimo że pożółkłe karty książek telefonicznych nie zmieniły się od czasów naszych pradziadków, a coraz to nowocześniejsze bazy danych co kilka lat wymyślają same siebie od nowa, wszystko opiera się na jednym fundamentalnym pomyśle – indeksach.

W tym artykule skoncentrujemy się na tym, jak indeksy pomagają efektywnie szukać informacji w dużych zbiorach danych. Zademonstrujemy, dlaczego w ogóle są potrzebne, oraz pokażemy coraz bardziej skomplikowane konstrukcje, które dają coraz lepsze efekty...

Zagadnienia poruszane w tym artykule:

• Po co to komu?
• Jak indeksować?
• Próba pierwsza: podejście naiwne;
• Próba druga: drzewo sufiksowe;
• Trochę teorii: błędy i ich rodzaje;
• Trochę teorii: błąd błędowi nierówny;
• Próba trzecia: index słów;
• Próba czwarta: N-Gramy.

Artykuł pochodzi z magazynu "Programista" nr 8/2018 (75). Jest to wydanie z przełomu października i listopada 2018. Szczegółowy spis treści: https://programistamag.pl/programista-8-2018-75/

Autorem artykułu jest Jarosław Jedynak. Rozpoczynał karierę jako programista, wyspecjalizował się w security. Do niedawna jako analityk malware w CERT Polska zajmował się między innymi inżynierią wsteczną złośliwego oprogramowania i automatyzacją jego analizy. Obecnie pracuje jako security engineer w Google, spędza czas na reverse-engineeringu oraz prowadzi badania nad nowymi sposobami wykrywania złośliwego oprogramowania. W wolnym czasie programuje do szuflady, gra w konkursy CTF i ogląda koty w Internecie.

>>FRAGMENT ARTYKUŁU DO POBRANIA<<