This paper addresses estimation of battery state-of-charge (SOC) from the joint perspectives of dynamic data-driven and model-based recursive analysis. The proposed SOC estimation algorithm is built upon the concepts of symbolic time series analysis (STSA) and recursive Bayesian filtering (RBF) that is a generalization of the conventional Kalman filtering. A special class of Markov models, called ×D-Markov (pronounced as cross D-Markov) machine, is constructed from a symbolized time-series pair of input current and output voltage. A measurement model of SOC is developed based on the features obtained from the ×D-Markov machine. Then, a combination of this measurement model and a low-order model of the SOC process dynamics is used for construction of the RBF. The proposed algorithm of SOC estimation has been validated on (approximately periodic) experimental data of (synchronized) current-voltage time series, generated from a commercial-scale lead-acid battery system.