Description
Given a line consists of two path, separated by a blank.
For example, ./a/b/c.html ./d/e/f/g.html.
Each path,
  • begins with ./.
  • consists of a directory and a filename part.
Given the line, ./pr1/sub1/slide2.html ./pr1/sub3/sub31/slide1.html, we want to find the shortest path, ../sub3/sub31/, to change from the first directory to the second one.
Raw Input Desired Output 
./pr1/sub3/sub31/slide1.html ./pr1/sub1/slide2.html
./top/index.html ./top/lecture1.html
./top/lecture1.html ./welcome.html
./top/lecture2.html ./pr1/sub1/slide1.html
./pr1/sub3/sub31/slide1.html ./pr2/slide1.html

../../sub1/

../
../pr1/sub1/
../../../pr2/
Script and Comments
Script1 
[ 1] s#/[^/ ]*( |$)#/\1#g
[ 2] s#^(\./[^ ]+/)([^ ]*) \1#\2 #
[ 3] s#^\./##
[ 4] :loop
[ 5] s#(/|^)[^/]+/ #\1 ../#
[ 6] t loop
[ 7] s#/./#/#
[ 8] s# ##
Comments
  1. The `-r' option of GNU sed must be used to make sed interpret REs as EREs.
  2. To prevent from escaping the slashes in the `s///' command, this script uses `#' to delimit RE and the replacement.
  3. Step [1] removes the filename part of each path, making ./pr1/sub3/sub31/slide1.html ./pr1/sub1/slide2.html be ./pr1/sub3/sub31/ ./pr1/sub1/.
    Note that two paths are separated by a blank.
  4. Step [2] removes the longest common prefix of both directories, making ./pr1/sub3/sub31/ ./pr1/sub1/ be sub3/sub31/ sub1/.
  5. Step [3] removes the possible ./ prefix of each directory if the substitution of Step [2] did not perform.
  6. Steps [4] thru [6] constitute a loop which replaces each subdirectory of the first path with `/../`, making ./sub3/sub31/ sub1/ be ../../sub1/.
  7. Step [7] replace /./ with /.
  8. Step [8] removes the blank used to separate two paths.