Excel 2003: An Attempt to Sort Sentences or Filenames by Identifying Multiword Phrases

I had a bunch of filenames.  I wanted to know which two-word phrases appeared most frequently.  The purpose of this effort was to put those filenames into categories.  I hoped that the approach of finding significant two-word phrases in those filenames would help me automate the file-sorting process.  This post describes the first approach I took to identify those two-word phrases.

Parsing the Filenames

I hoped that two-word phrases would be a good size.  I figured they would sort into many essentially one-word phrases (e.g., "a dog" would be trimmed to "dog," which would not have much significance) and a relatively small number of more significant two-word phrases (e.g., "big dog").   I hoped, that is, that I could easily filter the list for common words (a, an, the, if, of ...) and then count what was left.  It seemed, though, that I could still have taken approximately the approach described here if I had had been looking for three-word or longer phrases.

The approach would have been similar if I had been examining sentences instead of filenames.  I would have gotten the sentences into individual rows by using Microsoft Word and replacing sentence ends (e.g., ? ! .) with the same punctuation followed by ^p characters, which Word would interpret as the start of a new line, and then pasting the text into Excel.  It might have taken a while to resolve sentence ends, given problems with e.g., "Mr.".  I did not have more than 65,000 filenames, so Excel 2003 would handle it.  Otherwise, I might have needed a newer spreadsheet (e.g., the Calc programs in LibreOffice or OpenOffice).

Consider this sentence or filename:  "I saw a dog - a big dog."  Using spaces as delimiters (as I intended to do), its two-word phrases would be "I saw," "saw a," "a dog," "dog -," "- a," "a big," and "big dog."  This approach would produce some junk, but I hoped it would be easily filtered.  Not worrying about the punctuation seemed faster than trying to anticipate endless punctuation combinations (e.g., "dog -- a").  It would fail in some instances (e.g., "dog--a"), but those too seemed likely to involve insignificant phrases.

That sentence contains seven spaces.  I could count the number of spaces manually.  With many sentences, it would make more sense to use a formula.  One approach would be to use Excel's SUBSTITUTE and LEN functions to calculate the difference in length between the sentence with and without spaces, and then use MAX to see which row has the largest number of spaces.  TRIM would remove excess spaces.

Since each two-word pair would contain one space, the sample sentence would contain seven pairs of words.  Therefore, my spreadsheet needed enough columns to accommodate seven two-word phrases.  The approach I took was to set up the spreadsheet like this:

The top row indicated the number of the two-word phrase.  The first one was "I saw," in group 1.  The second row indicated the number of the space found.  For instance, the first space was at character position 2 (i.e., right after "I"), and the second space appeared at position 6 (after "saw").  This image shows only the first three groups; I would need four more.  As it shows, the first group required calculation of only two numbers because its starting point (character position 1) was already known.  I preferred this approach of breaking out the calculations visibly, rather than jamming them all together in one long, complicated formula.  It was usually faster this way, and it made it easier to spot errors.

I used formulas in the header rows to facilitate copying.  For instance, the formula in cell F2 was =F1, and in F1 it was =C1.  That way, once I worked out my formulas in row 3, I could select and copy cells F1 through I3 repeatedly across the spreadsheet, until I had enough column groups to accommodate all of the spaces in my longest filename or sentence.

To prepare the following list of formulas for the cells on row 3, I used a macro.  Those formulas were as follows:

C3	=FIND(" ",$A3)
D3	=FIND(" ",$A3,C3+1)
E3	=TRIM(LEFT(A3,D3))
F3	=IF(D3=LEN($A3),"",C3)
G3	=IF(F3="","",FIND(" ",$A3,F3+1))
H3	=IF(G3="","",IF(ISERROR(FIND(" ",$A3,G3+1)),LEN($A3),FIND(" ",$A3,G3+1)))
I3	=IF(H3="","",TRIM(MID($A3,F3,H3-F3+1)))
J3	=IF(H3=LEN($A3),"",G3)
K3	=IF(J3="","",FIND(" ",$A3,J3+1))
L3	=IF(K3="","",IF(ISERROR(FIND(" ",$A3,K3+1)),LEN($A3),FIND(" ",$A3,K3+1)))
M3	=IF(L3="","",TRIM(MID($A3,J3,L3-J3+1)))

So anyway, now I had a spreadsheet containing the two-word phrases that I wanted to sort and examine.  I made a backup and proceeded to convert the spreadsheet's formulas to values.  With the formulas frozen as values, I could sort and delete rows and columns without changing the results shown.  There appeared to be functions for this purpose in ASAP Utilities and possibly elsewhere.  An easy way to do this was to go to the top left-hand corner of the spreadsheet, hit Ctrl-A to select it all, and then hit Edit > Copy, Edit > Paste Special > Values > Enter > Enter.  I had usually found that the same keystrokes worked in later versions of Excel.  In this case, the keystrokes were Alt-E, C, Alt-E, S, V, Enter, Enter.

However achieved, the point is that cell C3 no longer contained the formula =FIND(" ",$A3).  Now it just contained the number 2, and it would continue to contain that number even if I deleted cell A3.  With that done, I could now delete the columns containing the numbers that I had used to detect my two-word phrases (e.g., columns C, D, F, G, H ...).  I sped up that process by doing a column sort (select all (Ctrl-A) and then Data > Sort > Options > Sort Left to Right > Row 2.  I put numbers at the tops of the Phrase columns, so as to keep their order straight.

Lining Up the Phrases

At this point, the cells toward the right side of my spreadsheet looked like this:

That is, the ends of the rows did not end at the same place.  In this illustration, the filename on row 2 had 17 two-word phrases, while the one on row 3 had only 16.  I wanted them all in a single column.  I wasn't sure if I needed them in proper order (in this example, P2, Q2, R2, followed by P3, Q3, R3), but I preferred that if possible.

I had tackled a similar problem previously.  That post still provided more details than I have written here.  But in some regards, I now saw a way to simplify that process a bit.  I deleted row 1, containing the column headings, as well as column 1, containing the original filenames.  They seemed unnecessary and potentially confusing at this point.  Then I created another worksheet (Insert > Worksheet).  Its default name was Sheet2.  In cell A1 in that worksheet, I entered a formula that referred to the corresponding cell in Sheet1, where my data were located.  The formula that I put into cell A1 in Sheet2 was =IF(LEN(Sheet1!A1)>0,CELL("address",Sheet1!A1),"").

That formula produced this output in Sheet2, cell A1:  [xA8.xls]Sheet1!$A$1.  (xA8.xls was the name of my spreadsheet file.)  I was going to use the preliminary information, the part that said [xA8.xls]Sheet1!, to tell the computer where a new entry began.  In other words, if the spreadsheet had given me just $A$1, I would have changed my formula so that Sheet2, cell A1 would contain something like this:  #$A$1.  Any odd character would have been sufficient in place of # as long as it gave the computer something unique to look for.

Next, I copied that formula from Sheet2, cell A1 to each cell that corresponded to my data in Sheet1.  In other words, in Sheet1 I hit Ctrl-End to discover that the bottom right corner of my spreadsheet was at cell Q14998.  So now, in Sheet2, I copied that formula from cell A1 to all cells down to Q14998.  A fast way to do that was to hit F5 and type Q14998 and hit Enter.  That took me to Q14998.  I put an X there.  Then I went back to A1 and hit Ctrl-C > Ctrl-Shift-End > Enter.  Boom!  Done.  I went back to Q14998 to double-check.  Then Alt-O, C, A to autofit the column widths.

Now I had a bunch of cells that had ugly stuff like cell A1 (above):  [xA8.xls]Sheet1!$A$1.  I hit Ctrl-A > Ctrl-C to copy it all.  I opened Notepad and hit Ctrl-V to paste it.  (If there had been too much data for Notepad, I think something like Notepad++ would have worked.)  The purpose of putting it into Notepad was to remove the column formatting.  (There were delays with some of these operations, as the Windows clipboard and the various programs wrapped their heads around the size of the task.)

Now I copied it all from Notepad to Microsoft Word.  Any editor would have worked, as long as it had a way of doing global search-and-replace operations that would produce line breaks.  That is, in Word, I replaced all instances of the ugly stuff (i.e., [xA8.xls]Sheet1!) with a newline character (^p).  Word reported that it had made about 170,000 replacements.  This gave me the desired list, starting like this:

$A$1

$B$1  

$C$1  

$D$1  

There were invisible tabs after the entries (e.g., it was actually $A$1 tab), and there were also some blank lines.  I cleaned these up with various ^p^p and ^t^p replace operations, repeated until there were no more.  The file was long -- about 3,700 pages.

I went back to Excel and deleted Sheet2:  I didn't need it anymore, and all its calculations would slow things down.  I created a new Sheet2 and pasted the results from Word into it.  I wasn't sure if Word had inserted any other funky invisible characters, so I ran the results through Notepad on the way home, just to be sure.

But now, oops, new problem.  My old Excel 2003 couldn't accommodate 170,000 rows.  It gave me an error:  "File not loaded completely."  I took a look.  Row 65536 contained a reference to $F$5911.  I could have transferred the whole project over to LibreOffice, which could handle 170,000 rows, but that would have been premature.  I had kept Notepad open, so now I searched for that item $F$5911 in the data that were still sitting there in Notepad.  I deleted everything down to that point, copied, and repeated in an adjacent column.  I had to do this a couple of times.  So now I had a spreadsheet that was three columns wide and 65,536 rows long.  Warning: do not print your results.

I inserted blank columns between these columns of output.  Those blank columns would contain the text corresponding to those cell references.  For instance, in Sheet2 cell A1, I now had $A$1.  So in the blank cell B1, I put this formula:  =INDIRECT("Sheet1!"&A1).  I copied that formula to all the other cells in those adjacent columns.  That gave me three sets of two columns each:  the first provided the reference, and the second containd my actual two-word phrase.

At this point, I froze all those values, as above, and deleted the reference columns.  So now I just had three columns containing two-word phrases.  In short, I had managed to isolate the phrases.  Now it was time to start slicing and dicing them.

Working with Unique Phrases

I wanted to filter those two-word phrases for unique ones.  For example, if there were a thousand two-word phrases that said "Email from," I wanted just one entry of that nature, with a numerical companion cell containing the number 1,000.

To do that filtering, I tried to use LibreOffice Calc, where I could get all that material into column A.  But Calc hung for about 15 hours before producing output.  (Excel also hang at a number of points in this whole process.)  I did not test Calc's output, but it appeared to have given me some repetitive items in that supposedly nonrepetitive list.  I went back to Excel, filtering each of the three columns and then combining the short output into one column and filtering that.  This gave me 7,539 unique two-word phrases.  That list passed the test for duplicates, but counts indicated that it was not accounting for all 169,891 two-word phrases.  The formulas to do those counts really slowed things down, so I deleted them for the moment.

I thought that it might help to clean up unnecessary characters.  I sorted each of the three columns according to starting and ending characters, so as to detect extraneous ones (e.g., various kinds of brackets, quotation marks, and other symbols).  I also did some global (Ctrl-H) searches in Excel to the same effect.  In addition, I deleted a few meaningless two-word pairs.  These efforts exposed me to the fact that many two-word phrases would consist, at least in part, of single letters (e.g., "A dog," "Roger P").  It seemed that I probably should have done global replace operations, even before breaking out the two-word phrases, so as to promote meaningful two-word combinations (e.g., "Roger P" and "P Smith" might be less recognizable than "Roger Smith").  Possibly a preliminary search for three- and even four-word proper nouns would have been a good approach there.

I also decided, along the way, that it would make sense to tolerate meaningful one-word terms (e.g., the "Pentium" word that would remain after removing the unhelpful "a" from "a Pentium").  That predictable conclusion raised questions about my sequence of steps generally.

After those cleanup efforts, I filtered again for unique two-word phrases and counted their occurrences.  Working with three source columns required some extra steps, mostly to eliminate duplicates, but ultimately my count of items found from searches for unique items was within 1% of the actual number of such items.  In other words, my filtering for unique items substantially accounted for all items.  Specifically, I had 163,391 two-word phrases, and in some apparent overcounting, my list of unique phrases accounted for 163,772 such phrases.

Because those counts did not jibe perfectly, I decided to take an elimination approach -- that is, to remove the two-word phrases that lacked significance, rather than selecting those that had it.  To help me in this process, I divided the two-word phrases into individual words, and then prepared to test each of them against a list of relatively insignificant words that I had cooked up for the occasion.  Before doing that, I had to screen again for stray punctuation (now that e.g., a comma had emerged in "soon, however" such that "soon," would not be found in an elimination of "soon") -- making it increasingly appealing to find some way of doing that earlier in the process.  Another step that would have been beneficially taken earlier, to the extent possible, would have been to convert date references (e.g., "2-13-09 project" vs. "Feb. 13 project") into a standard format, or else decide that none were significant.  It seemed, generally, that renaming the files to standardize various names and terms (or at least revising aliases for them) should have occurred earlier in the process.  Such changes seemed likely to shape this sentence-parsing process.  For instance, if full names were to be used (e.g., "Roger P. Smith"), then a two- rather than three-word focus could be wrongheaded.

Project Abortion

At this point, I had an unpleasant realization.  The need to pare down my spreadsheet, so as not to have to wait forever for calculations, and the loss of concentration due to long waits and the passage of time, had produced a situation where I had not realized that, in the past several hours, my work had ceased to be directly linkable back to the original list of files.  There was no index.  Worse, there had been global changes to remove troublesome punctuation, further reducing direct linkability.  I could continue with this effort, using backups to reconstruct the links.  But there seemed to be good reasons to reconceive the whole approach.

One emerging conclusion was that there just might not be a shortcut to a good rubric or other structured approach to the renaming of files, the coding of sentences, or the constructing of aliases for bits of text being examined in this kind of effort.  One question in that regard was whether there would be a good way to identify and change troublesome characters or combinations of characters up front.  That question led me to a second try.

Sorting and Manipulating a Long Text List to Eliminate Some Files

In Windows XP, I made a listing of all of the files on a hard drive.  For that, I could have typed DIR *.* > OUTPUTFILE.TXT, but instead I used PrintFolders.  I selected the option for full pathnames, so each line in the file list was like this:  D:\FOLDER\SUBFOLDER\FILENAME.EXT, along with date and file size information.

I wanted to sort the lines in this file list alphabetically.  They already were sorted that way, but DIR and PrintFolders tended to insert blank lines and other lines (e.g., "=======" divider lines) that I didn't want in my final list.  The question was, how could I do that sort?  I tried the SORT command built into WinXP, but it seemed my list was too long.  I tried importing OUTPUTFILE.TXT into Excel, but it had more than 65,536 lines, so Excel couldn't handle it.  It gave me a "File not loaded completely" message.  I tried importing it into Microsoft Access, but it ended with this:

Import Text Wizard

Finished importing file 'D:\FOLDER\SUBFOLDER\OUTPUTFILE.TXT to table 'OUTPUTTXT'.  Not all of your data was successfully imported.  Error descriptions with associated row numbers of bad records can be found in the Microsoft Office Access table 'OUTPUTFILE.TXT'.

And then it turned out that it hadn't actually imported anything.  At this point, I didn't check the error log.  I looked for freeware file sorting utilities, but everything was shareware.  I was only planning to do this once, and didn't want to spend $30 for the privilege.  I did download and try one shareware program called Sort Text Lists Alphabetically Software (price $29.99), but it hung, probably because my text file had too many lines.  After 45 minutes or so, I killed it.

Eventually, I found I was able to do the sort very quickly using the SORT command in Ubuntu.  (I was running WinXP inside a VMware virtual machine on Ubuntu 9.04, so switching back and forth between the operating systems was just a matter of a click.)  The sort command I used was like this:

sort -b -d -f -i -o SORTEDFILE.TXT INPUTFILE.TXT

That worked.  I edited SORTEDFILE.TXT using Ubuntu's GEDIT program (like WinXP's Notepad).  For some reason, PrintFolders (or something) had inserted a lot of lines that did not match the expected pattern of D:\FOLDER\SUBFOLDER\FILENAME.EXT.  These may have been shortcuts or something.  Anyway, I removed them, so everything in SORTEDFILE.TXT matched the pattern.

Now I wanted to parse the lines.  My purpose in doing the file list and analysis was to see if I had any files that had the same names but different extensions.  I suspected, in particular, that I had converted some .doc and .jpg files to .pdf and had forgotten to zip or delete the original .doc and .jpg files.  So I wanted to get just the file names, without extensions, and line them up.  But how?  Access and Excel still couldn't handle the list.

This time around, I took a look at the Access error log mentioned in its error message (above).  The error, in every case, was "Field Truncation."  According to a Microsoft troubleshooting page, truncation was occurring because some of the lines in my text file contained more than 255 characters, which was the maximum Access could handle.  I tried importing into Access again, but this time I chose the Fixed Width option rather than Delimited.  It only went as far as 111 characters, so I just removed all delimiting lines in the Import Text Wizard and clicked Finish.  That didn't give me any errors, but it still truncated the lines.  Instead of File > Get External Data > Import, I tried Access's File > Open command.  Same result.

I probably could have worked through that problem in Access, but I had not planned to invest so much time in this project, and anyway I still wasn't sure how I was going to use Access to remove file extensions and folder paths so that I would just have filenames to compare.  I generally used Excel rather than Access for that kind of manipulation.  So I considered dividing up my text list into several smaller text files, each of which would be small enough for Excel to handle.  I'd probably have done that manually, by cutting and pasting, since I assumed that a file splitter program would give me files that Excel wouldn't recognize.  Also, to compare the file names in one subfile against the file names in another subfile would probably require some kind of lookup function.

That sounded like a mess, so instead I tried going at the problem from the other end.  I did another directory listing, this time looking only for PDFs.  I set the file filter to *.pdf in PrintFolders.  I still couldn't fit the result into Excel, so I did the Ubuntu SORT again, this time using a slightly more economical format:

sort -bdfio OUTPUTFILE.TXT INPUTFILE.TXT

This time, I belatedly noticed that PrintFolders and/or I had somehow introduced lots of duplicate lines, which would do much to explain why I had so many more files than I would have expected.  As advised, I used another Ubuntu command:

sort OUTPUTFILE.TXT | uniq -u

to remove duplicate lines.  But this did not seem to make any difference.  Regardless, after I had cleaned out the junk lines from OUTPUTFILE.TXT, it did all fit into Excel, with room to spare.  My import was giving me lots of #NAME? errors, because Excel was splitting rows in such a way that characters like "-" (which is supposed to be a mathematical operator) were the first characters in some rows, but were followed by letters rather than numbers, which did not compute.  (This would happen if e.g., the split came at the wrong place in a file named "TUESDAY--10AM.PDF."  So when running the Text Import Wizard, I had to designate each column as a Text column, not General.

I then used Excel text functions (e.g., MID and FIND) on each line, to isolate the filenames without pathnames or extensions.  I used Excel's text concatenations functions to work up a separate DIR command for each file I wanted to find.  In other words, I began with something like this:

D:\FOLDER\SUBFOLDER\FILENAME.EXT

and I ended with something like this:

DIR "FILE NAME."* /b/s/w >> OUTPUT.TXT

The quotes were necessary because some file names have spaces in them, which confuses the DIR command.  I forget what the /b and other options were about, but basically they made the output look the way I wanted.  The >> told the command to put the results in a file called OUTPUT.TXT.  If I had used just one > sign then that would have meant I wanted OUTPUT.TXT to be recreated every time a match was found.  Using two >> signs was an indication that OUTPUT.TXT should be created if it does not yet exist, but otherwise the results of the command should just be appended to whatever is already in OUTPUT.TXT.

In cooking up the final batch commands, I would have been helped by the MCONCAT function in the Morefunc add-in, but I didn't know about it yet.  I did use Morefunc's TEXTREVERSE function in this process, but I found that it would crash Excel when the string it was reversing was longer than 128 characters.  Following other advice, I used Excel's SUBSTITUTE command instead.

I took the thousands of resulting commands (such as the DIR FILENAME.* >> OUTPUT.TXT shown above), one for each file type (e.g., FILE NAME.*) that I was looking for, into a DOS batch file (i.e., a text file created in Notepad, with a .bat extension, saved in ANSI format) and ran it.  It began finding files (e.g., FILENAME.DOC, FILENAME.JPG) and listing them in OUTPUT.TXT.  Unfortunately, this thing was running very slowly.  Part of the slowness, I thought, was due to the generally slower performance of programs running inside a virtual machine.  So I thought I'd try my hand at creating an equivalent shell script in Ubuntu.  After several false starts, I settled on the FIND command.  I got some help from the Find page in O'Reilly's Linux Command Directory, but also found some useful tips in Pollock's Find tutorial.  It looked like I could recreate the DOS batch commands, like the example shown above, in this format:

find -name "FILE NAME.*" 2>/dev/null | tee -a found.txt

The "-name" part instructed FIND to find the name of the file.  There were three options for the > command, called a redirect:  1> would have sent the desired output to the null device (i.e., to nowhere, so that it would not be visible or saved anywhere), which was not what I wanted; 2> sent error messages (which I would get because the lost+found folder was producing them every time the FIND command tried to search that folder) to the null device instead; and &> would have sent both the standard output and the error messages to the same place, whatever I designated.  Then the pipe ("|") said to send everything else (i.e., the standard output) to TEE.  TEE would T the standard output; that is, it would send it to two places, namely, to the screen (so that I could see what was happening) and also to a file called found.txt.  The -a option served the same function as the DOS >> redirection, which is also available in Ubuntu's BASH script language, which is what I was using here:  that is, -a appended the desired output to the already existing found.txt, or created it if it was not yet existing.  I generated all of these commands in Excel - one for each FILE NAME.* - and saved them to a Notepad file, as before.  Then, in Ubuntu, I made the script executable by typing "chmod +x " at the BASH prompt and then ran it by typing "./" and it ran.  And the trouble proved to be worthwhile:  instead of needing a month to complete the job (which was what I had calculated for the snail's-pace search underway in the WinXP virtual machine), it looked like it could be done in a few hours.

And so it was.  I actually ran it on two different partitions, to be sure I had caught all duplicates.  Being cautious, I had the two partitions' results output to two separate .txt files, and then I merged them with the concatenation command:  "cat *.txt > full.lst."  (I used a different extension because I wasn't sure whether cat would try to combine the output file back into itself.  I think I've had problems with that in DOS.)  Then I renamed full.lst to be Found.txt, and made a backup copy of it.

I wanted to save the commands and text files I had accumulated so far, until I knew I wouldn't need them anymore, so I zipped them using the right-click context menu in Nautilus.  It didn't give me an option to simultaneously combine and delete the originals.


Next, I needed to remove duplicate lines from Found.txt.  I now understood that the command I had used earlier (above) had failed to specify where the output should go.  So I tried again:

sort Found.txt | uniq -u >> Sorted.txt

This produced a dramatically shorter file - 1/6 the size of Found.txt.  Had there really been that many duplicates?  I wanted to try sorting again, this time by filename.  But, of course, the entries in Sorted.txt included both folder and file names, like this:

./FOLDER1/File1.pdf
./SomeotherFolder/AAAA.doc

Sorting normally would put them in the order shown, but sorting by their ending letters would put the .doc files before the .pdfs, and would also alphabetize the .doc files by filename before foldername.  Sorting them in this way would show me how many copies of a given file there had been, so that I could eyeball the possibility that the ultimate list of unique files would really be so much shorter than reported in Found.txt.  I didn't know how to do that in bash, so I posted a question on it.


Meanwhile, I found that the output of the whole Found.txt file would fit into Excel.  When I sorted it, I found that each line was duplicated - but only once.  So plainly I had done something wrong in arriving at Sorted.txt.  From this point, I basically did the rest of the project in Excel, though it belatedly appeared that there were some workable answers in response to my post.