Autocorrect algorithm - How to implement a decent "apostrophe & elision" feature? shorter version of the original question (as requests in comments)

What is the algorithm to handle missing apostrophe as it is done in auto-correct feature of Android virtual keyboard?

(If it helps / makes sense, feel free to give info about how such feature handles the detection and 2 words being written without any space between them?)

I need this in French where this happens much more than in English.

Example

Jai -&gt; J'ai ('I have' in French)


Regex could be part of the solution?

Here are some regex to recognize the beginning of some (french) words, but these do generate way too many false positive candidates

\b(c)(h?[aeiou])
\b(j)(h?[aeiou])
\b(n)(h?[aeiou])
\b(m)(h?[aeiou])
\b(t)(h?[aeiou])
\b(s)(h?[aeiou])
\b(l)(h?[aeiou])
\b(d)(h?[aeiou])
\b(qu)(h?[aeiou])


Note:
For sake of completeness, I alreay have the 2 remaining simple cases already covered in the dictionary xml file

&lt;word src="sil"&gt;s'il&lt;/word&gt;
&lt;word src="sils"&gt;s'ils&lt;/word&gt;




Keeping original question for reference purposes:

Context

Using the opensource AnyosftKeyboard keayboard provider app, I would like to add an "elision/apostrophe" feature to make it aware of missing apostrophe in typed word and add it in the frame of its autocorrect feature.

A word about apostrophe &amp; elision

"The apostrophe in French is used to replace a final vowel which is not pronounced because the next word also start with a vowel or silent “h”. The removing of a final silent vowel is called the ELISION. 

In written French, elision takes place only with the following words : ce, je, ne, me, te, se, le, la, de, que, and si (only with “il” and “ils”)."

Source, where you can read more for some examples: https://frenchforenglishhindispeakers.wordpress.com/2012/09/25/lapostrophe/

Example

He is my friend -&gt; Ce est mon ami (incorrect)
'Ce' is followed by 'est' -&gt; elision (deletion) of the 'e' of 'Ce')
                -&gt; C'est mon ami (correct)


Goal

Given the former example, I would like to implement a feature that would detect

Cest


and replace it by

C'est


That would allow the user to type faster by just ignoring apostrophe.
This behavior is already implemented in default Android keyboard

Questions

1 - What would be a proper algorithm to implement this "apostrophe &amp; elison" feature?
 2 - How is this feature implemented in Android keyboard(s)?

PS

I am not sure if this is the right place to ask such question. If not, please let me know where I should ask it. Thanks.
You've asked two questions: about what algorithm can be used, and how it is implemented in Android.  Only the former is on-topic here, so I'll answer the former.  (Also, our guidelines are that you should generally ask only one question per post.)



Suppose French has the rule that the two words "X Y" are always replaced by an elided single-word replacement if X is one of ce, je, ne, me, te, se, le, la, de, que, or si and if Y starts with a vowel or silent "h".  I don't know French well enough to know if this is indeed the rule, so I'll assume that's how French works.

To suggest elisions, you could precompute a mini-dictionary of all words Y that start with a vowel or silent "h".  Then, it is easy to search all text entered to see whether it contains a pair of words of the form "X Y" where X is one of ce, je, ne, me, te, se, le, la, de, que, or si and Y is in the mini-dictionary.  If you find such a pair, then you can programmatically generate the correct elision and automatically suggest it.  This should be straightforward to implement.

Precomputing the mini-dictionary should be feasible.  It should be easy to find a dictionary of all valid French words and identify which ones start with a vowel and which ones start with an "h".  The trickiest bit is you'll need a way to identify all French words that start with a silent "h".  I don't know enough about French to know whether there's a clever way to do that.  However, a brute-force method is probably sufficient: I expect it would be sufficient to do it manually (list all words that start with a "h" and identify which have a silent "h"), or crowdsource it (something like Amazon Mechnical Turk, targeted at native French speakers).  This only needs to be done once, so generating the mini-dictionary should be feasible.



I'll also mention a complementary method that's probably also worth adopting.  Compute the list of all elisions, as above (by iterating over all valid pairs "X Y" that will trigger elision, then programmatically computing the correct elision).  Then, add each possible elided form listed above to your spelling dictionary.  In other words, extend your dictionary to include all valid elisions that can ever be encountered.  This may be a useful supplement to the method above, as it will help detect typos when people try to type in the elided form but make a small mistake.

These two methods are complementary.  In particular, if someone types the unelided form (e.g., "Ce est"), the first method above will auto-suggest correcting that to the elided form ("C'est").  And, if someone tries to type the elided form but makes a typo (e.g., "C'ext"), the second method will auto-suggest how to correct the typo ("C'est").  You can decide whether both of those problems are important to solve, or whether you only want to solve one of these two problems, and use that to determine which of these methods to implement.