You might not want to full text index each column: full text search works best when searching over the 'full text' 😉

One approach would be to full text index a column containing the entire address, and then generate a full text query from the user's input.

For example, a column containing the string "123 Apple street, Tampa FL 33647" could be searched with a query like CONTAINSTABLE(table, column, N'123 AND Apple AND Street AND FL AND 33647', 50). That would return the top 50 ranked matches with all the search terms exactly. You could add prefix searches, weighting using ISABOUT, and so on just by varying the syntax of the full text query.