<commit_before>\chapter{Implementace}
Pro implementaci programu převádějícího OSM data do formátu vyhledávacího grafu
jsme zvolili v první části Python, protože pro něj existuje široké množství
knihoven, které nám pomohly při řešení jednotlivých dílčích problémů. Při
vytváření spojek mezi cestami a jejich následné kontrole již ale nedostačoval,
proto tuto a další části jsme implementovali v jazyce C. Mezi těmito částmi
předáváme data pomocí Protocol Bufferu v souboru. Vyhledávání je také
implementováno v jazyce C kvůli rychlosti a paměťové nenáročnosti.

\section{Použité knihovny a pomocné programy}
Během implementace programu pro přípravu dat jsme se snažili použít co nejvíce
již existujících knihoven a programů pro jednotlivé řešené problémy. Všechny
tyto knihovny a programy jsou nutné pro spuštění a používání programu. 

\medskip
\noindent Používáme tyto pomocné programy:
\begin{itemize}
	\item Výřez s městem z dat pro republiku vyrábíme pomocí 
	{\tuc Osmconvert} (GNU AGPL)\footurl{http://wiki.openstreetmap.org/wiki/Osmconvert}.
	\item Pro práci s Protocol Buffery v Pythonu využíváme třídy generované
	kompilátorem {\tuc protoc} (BSD	New).\footurl{http://code.google.com/p/protobuf/}.
	\item Pro práci s Protocol Buffery v C využíváme funkce a struktury
	generované kompilátorem {\tuc protobuf-c} 
	(BSD 2-Clause)\footurl{https://github.com/protobuf-c/protobuf-c}.
\end{itemize}

\noindent V programech napsaných v Pythonu využíváme následující knihovny:
\begin{itemize}
	\item Na parsování konfiguračních souborů používáme 
	{\tuc PyYAML} (MIT)\footurl{http://pyyaml.org/wiki/PyYAML}.
	\item Na parsování OSM XML používáme {\tuc imposm.parser} 
	(Apache)\footurl{http://imposm.org/docs/imposm.parser/latest/}.
	\item Souřadnice konvertujeme pomocí {\tuc pyproj}
	(MIT)\footurl{http://code.google.com/p/pyproj/}.
	\item Pro hledání komponent grafu využíváme {\tuc networkx} 
	(BSD)\footurl{http://networkx.github.io/}.
\end{itemize}

\noindent V programech napsaných v C využíváme následující knihovny:
\begin{itemize}
	\item Datové struktury, dynamická pole a další potřebné funkce zajišťuje
	{\tuc LibUCW} (GNU LGPL)\footurl{http://www.ucw.cz/libucw/}.
	\item Výpočty se zeměpisnými souřadnicemi provádí {\tuc GeographicLib}
	(MIT)\footurl{http://geographiclib.sourceforge.net/}.
\end{itemize}

Program osmconvert a knihovna GeographicLib jsou již zahrnuty ve zdrojovém kódu,
ostatní knihovny je potřeba zajistit v systému.

\section{Příprava dat}

\section{Klasifikace OSM dat}
\section{Vyřešení multipolygonů}
\section{Zjednodušení budov}
\section{Rozdělení dlouhých úseků}
\section{Spojky mezi cestami}
\section{Zkratky přes průchozí prostranství}
\section{Vytvoření vyhledávacího grafu}<commit_msg>Added text about used data structures.<commit_after>\chapter{Implementace}
Pro implementaci programu převádějícího OSM data do formátu vyhledávacího grafu
jsme zvolili v první části Python, protože pro něj existuje široké množství
knihoven, které nám pomohly při řešení jednotlivých dílčích problémů. Při
vytváření spojek mezi cestami a jejich následné kontrole již ale nedostačoval,
proto tuto a další části jsme implementovali v jazyce C. Mezi těmito částmi
předáváme data pomocí Protocol Bufferu v souboru. Vyhledávání je také
implementováno v jazyce C kvůli rychlosti a paměťové nenáročnosti.

\section{Použité knihovny a pomocné programy}
Během implementace programu pro přípravu dat jsme se snažili použít co nejvíce
již existujících knihoven a programů pro jednotlivé řešené problémy. Všechny
tyto knihovny a programy jsou nutné pro spuštění a používání programu. 

\medskip
\noindent Používáme tyto pomocné programy:
\begin{itemize}
	\item Výřez s městem z dat pro republiku vyrábíme pomocí 
	{\tuc Osmconvert} (GNU AGPL)\footurl{http://wiki.openstreetmap.org/wiki/Osmconvert}.
	\item Pro práci s Protocol Buffery v Pythonu využíváme třídy generované
	kompilátorem {\tuc protoc} (BSD	New).\footurl{http://code.google.com/p/protobuf/}.
	\item Pro práci s Protocol Buffery v C využíváme funkce a struktury
	generované kompilátorem {\tuc protobuf-c} 
	(BSD 2-Clause)\footurl{https://github.com/protobuf-c/protobuf-c}.
\end{itemize}

\noindent V programech napsaných v Pythonu využíváme následující knihovny:
\begin{itemize}
	\item Na parsování konfiguračních souborů používáme 
	{\tuc PyYAML} (MIT)\footurl{http://pyyaml.org/wiki/PyYAML}.
	\item Na parsování OSM XML používáme {\tuc imposm.parser} 
	(Apache)\footurl{http://imposm.org/docs/imposm.parser/latest/}.
	\item Souřadnice konvertujeme pomocí {\tuc pyproj}
	(MIT)\footurl{http://code.google.com/p/pyproj/}.
	\item Pro hledání komponent grafu využíváme {\tuc networkx} 
	(BSD)\footurl{http://networkx.github.io/}.
\end{itemize}

\noindent V programech napsaných v C využíváme následující knihovny:
\begin{itemize}
	\item Datové struktury, dynamická pole a další potřebné funkce zajišťuje
	{\tuc LibUCW} (GNU LGPL)\footurl{http://www.ucw.cz/libucw/}.
	\item Výpočty se zeměpisnými souřadnicemi provádí {\tuc GeographicLib}
	(MIT)\footurl{http://geographiclib.sourceforge.net/}.
\end{itemize}

Program osmconvert a knihovna GeographicLib jsou již zahrnuty ve zdrojovém kódu,
ostatní knihovny je potřeba zajistit v systému.

\section{Datové struktury}
V průběhu celé přípravy vyhledávacích dat často využíváme několik struktur,
které nyní popíšeme. Datové struktury využívané jen v konkrétních případech
popíšeme u těchto případů.

Při přípravě dat používáme několik {\tuc hešovacích tabulek}. Často potřebujeme
získat uzel respektive cestu s konkrétním identifikátorem, pro tento účel nám
slouží tabulky \verb|nodesIdx| respektive \verb|waysIdx|. V Pythonu jsou
reprezentovány typem slovník, v C využíváme součást knihovny libUCW
\verb|hashtable|. V obou případech je klíčem OSM identifikátor objektu a
hodnotou index do pole uzlů resp. cest, kde je daný objekt uložen.

U každé cesty je v datech uložen seznam uzlů, přes které prochází. Je ale vhodné
mít i pro každý vrchol uložen seznam cest, které jím prochází. Pro tento účel
máme seznam \verb|nodeWays|. Je to seznam seznamů, kdy pod indexem $i$ je seznam
všech identifikátorů cest, které prochází vrcholem na indexu $i$. V Pythonu jde
o seznam seznamů, v C je to rostoucí pole rostoucích polí z libUCW.

Během zpracování hledáme uzly blízké daným uzlů. Abychom pro každé takové
hledání nemuseli procházet všechny uzly, vytvoříme si na začátku {\tuc mřížku}.
Tato mřížka dělí plochu mapy na čtverce $20 \times 20$\,m a v každém čtverci si
uložíme seznam identifikátorů vrcholů, které v něm leží. Poté nám při hledání
sousedů bodu stačí zjistit, do kterého čtverce patří a následně prohledat jen
několik okolních čtverců.

V Pythonu se jedná o třídu \verb|Raster|, která při vytvoření vyrobí mřížku z
mapy. Mřížka je uložena v atributu \verb|raster|, třída má metodu
\verb|getBox(lon,lat)|, která pro bod s  délku \verb|lon| a šířku \verb|lat|
vrátí tuple se souřadnicemi buňky, ve které se bod nachází. Mřížka \verb|raster|
je seznam seznamů seznamů.

V C je mřížka reprezentována strukturou \verb|raster_t|. Samotná mřížka je prvek
\verb|raster| této struktury. V souboru \verb|raster.h| jsou definovány funkce
pro práci s mřížkou. Funkce \verb|makeRaster(map_t map)| vyrobí z mapy mřížku a
vrátí ji. Funkce \verb|getRasterBox(raster_t raster, int64_t lon, int64_t lat)|
dostane jako paramter mřížku, délku a šířku bodu a vrátí pole se dvěma prvky --
souřadnicemi buňky, kde se bod nachází. Mřížka \verb|raster| je reprezentována
rostoucím polem rostoucích polí rostoucích polí z knihovny libUCW.

\medskip


\section{Stažení dat OSM}
Abychom mohli připravovat data pro vyhledávání, musíme nejprve získat data OSM
pro dané město. O tuto činnost se stará skript \verb|prepare.sh|, který stáhne
data pro celou Českou republiku a pomocí osmconvert z ní vyřízne obdélník s
městem. Ten uloží jako \verb|praha.osm|\footnote{Program byl připravován pro vyhledávání tras po Praze, proto soubory obvykle
obsahují název praha.} k dalšímu zpracování.

\section{Klasifikace dat}

\section{Vyřešení multipolygonů}
\section{Zjednodušení budov}
\section{Rozdělení dlouhých úseků}
\section{Spojky mezi cestami}
\section{Zkratky přes průchozí prostranství}
\section{Vytvoření vyhledávacího grafu}
{'fraction_non_alphanumeric': 0.0728621822162754, 'fraction_numerical': 0.001216397031991242, 'mean_word_length': 5.041146216017634, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 2, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6506335', 'n_tokens_mistral': 3474, 'n_tokens_neox': 3627, 'n_words': 980}