para hacerlo mas facil, a la tabla de categorias que ya tienes: agrega un campo que bien se puede llamar URL, donde incluyas preferentemente URL sin espacios(puedes usar guion) y en minusculas.
luego en el link no vas a imprimir categoria.php?=[ctg_id] si no: href="/[ctg_url/" y de esta manera te aparecera la URL
www.pagina.com/[ctg_url], no pienses que imprimes categoria.php?=4 y htaccess la cambiara, eso tienes que hacerlo en el codigo manualmente.
para las subcategorias tendras que ingeniarlas para que la url quede
www.pagina.com/categoria/subcategoria jugando con los valores de htaccess y asi como te muestran en el ejemplo obteniendo 1 valor $1, obtener $2 que sera la id o url de subcategoria y trabajaras con ella