What I remember is that it sounded like pretty simple lookups. As you typed, the software compared your word to, essentially, a weighted dictionary to guess what you were going to type next.
If you typed “b” it was flummoxed. But if you typed “behav” it knew the next letter was almost certainly going to be “e” or “i” (for behavior). It may have been more complicated than that, but probably not much. It was 2007 and the phone CPU was not powerful.
One interesting thing I remember is that they said the phone enlarged the touch targets for highly predicted next letters. For example it would be easier to type an “e” than a “w” after you had typed “behav”, because the tap boundary expanded around the “e”. Cool stuff!
And if you did type behavw and hit space, it would autocorrect to behave.
At some point I recall Apple announcing that they had switched autocorrect to a full machine learning implementation. Rather than a simple deterministic look-up, it was trained on a huge corpus of text, and reads the whole chunk of what you’ve written so far to make predictions. Everyone does this now, it’s how they deliver the (incredibly annoying and stupid IMO) one-tap suggestions for email and text replies. “Thanks!” “Noted.” “I’ll get right on that.”
In my memory, that’s when typing got a lot more annoying on iPhones. The quality of suggestions went either down or weirdo or both. For example it just tried to sub-in “Quaker” for “quality” in the previous sentence. Why??